素因数分解(Prime-Factor)

説明

素因数分解を行う。

計算量

• $O(\sqrt N)$

実装例

• prime_factor($n$):= 自然数 $n$ を素因数分解した結果を返す。

map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

検証

AOJ NTL_1_A 素因数分解

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A"

#include "../../template/template.cpp"

#include "../prime-factor.cpp"

int main() {
  int N;
  cin >> N;
  cout << N << ":";
  for(auto p : prime_factor(N)) {
    while(p.second--) cout << " " << p.first;
  }
  cout << endl;
}