素因数分解
1つの正整数に対しては試し割り法で
$ O(\sqrt{N})
$ N
以下の正整数についての複数のクエリに対しては
SPF
を利用して
前処理：
$ O(NloglogN)
クエリ：
$ O(logN)
SPF（最小素因数）の配列は、
エラトステネスの篩
でboolを入れたところに素因数を入れると作れる。ある数
$ K
に対して、
$ K
をSPFで割る→商を
$ K_1
としてそのSPFで割る……と繰り返せば高速に素因数分解ができる。
リファレンス
素因数分解のアルゴリズム / アルゴリズムロジック