素因数分解
説明
順番に探索していく単純な素因数分解。
計算量
O(N0.5)
使い方
factorize(n)でnを素因数分解した結果をmap<素因数,回数>で返す。
必要なライブラリ
- map
ソースコード
素因数分解
map<int, int> fractorize(int n) {
map<int, int> m;
for (int i = 2; i * i <= n; i++)
for (; !(n % i); m[i]++) n /= i;
if (1 < n) m[n]++; return m;
}
確認
なし
