素因数分解
(math/prime-factorize.hpp)

• View this file on GitHub
• Last update: 2022-11-22 13:26:41+09:00
• Include: #include "math/prime-factorize.hpp"
• Link: View error logs on GitHub Actions

Verified with

• verify/AOJ-NTL_1_A.test.cpp

Code

#pragma once
template <class T>
map<T, int> primeFactorize(T n) {
  map<T, int> res;
  for(T i = 2; i * i <= n; ++i){
    while(n % i == 0){
      ++res[i];
      n /= i;
    }
  }
  if(n != 1) res[n] = 1;
  return res;
}

#line 2 "math/prime-factorize.hpp"
template <class T>
map<T, int> primeFactorize(T n) {
  map<T, int> res;
  for(T i = 2; i * i <= n; ++i){
    while(n % i == 0){
      ++res[i];
      n /= i;
    }
  }
  if(n != 1) res[n] = 1;
  return res;
}

Back to top page