エラトステネスのふるいと高速素因数分解
エラトステネスのふるいとは
エラトステネスのふるいは，ある正の整数\(N\)以下の素数をすべて見つけ出すアルゴリズムです．次の操作により，素数を見つけ出します．
- \(2\)から\(N\)までの整数すべてを素数候補とする．
- 素数候補の数のなかで最小のもの\(p\)とする．\(p\)は素数であることが確定するので，素数候補から取り出す．
そして，\(p\)の倍数を素数候補から消去する． - 2.の操作を繰り返し，\(p\)が\(\sqrt{N}\)を超えたら終了する．操作終了までに取り出した数と素数候補として生き残っている数が素数である．
計算量は\(O(N \log \log N)\)であることが知られています．
エラトステネスのふるいをC++で実装
上記のコードは，エラトステネスのふるいをC++で実装した例です．sieve関数内の配列isprimeで素数候補を管理し（isprime[i]==trueならiは素数），2から順に素数を見つけていきます．
高速な素因数分解（エラトステネスのふるいの応用・osa_k法）
ある正の整数\(N\)を素因数分解するとき，愚直にやると\(O(\sqrt{N})\)程度の時間がかかります．
\(N\)以下の正の整数すべてを素因数分解しようとすれば，\(O(N \sqrt{N})\)程度の時間がかかることになりますが，なんとかして時間短縮したい場面もあるでしょう．
そこで登場するのが，osa_k法と呼ばれる方法です．
osa_k法とは
osa_k法は，次のようにして\(N\)以下の正の整数を素因数分解するアルゴリズムです．
（前処理） 次の手順で，\(N\)以下の正の整数\(i \quad (i = 1, 2, \dots , N)\)について最小の素因数（\(i\)を割り切る最小の素数）\(min\_factor(i)\)を求める．
- \(2\)以上\(N\)以下の各整数\(i\)について，一旦\(min\_factor(i)=i\)とする．
- \(min\_factor(i)==i\)である場合は，\(i\)の倍数\(k\)について\(min\_factor(k) > i\)ならば\(min\_factor(k) = i\)とする．
この操作を，\(i\)以外の\(i\)の倍数全てに対して行う． - 2.の操作を\(2\)から順番に行い，\(i\)が\(\sqrt{N}\)を超えたら終了する．
※操作終了時，\(2 \leq i\)かつ\(min\_factor(i) == i\)となっている数\(i\)が素数である．
（本計算） 次の手順で，\(2\)以上\(N\)以下のある正の整数\(M\)を素因数分解する．
- \(k = M\)とする．
- \(min\_factor(k)\)は\(k\)の素因数であるから，これを答えとしてメモしておく（答えの配列に追加する）．
その後，\(k\)を\(min\_factor(k)\)で割った商を新たな\(k\)とする． - 2.の操作を，\(k\)が2以上である限り繰り返す．
操作終了時に答えの配列に格納されている数が，\(M\)の素因数である．
osa_k法の計算量
\(N\)以下の正の整数について素因数分解する場合の計算量を考えます．
osa_k法の前処理は，エラトステネスのふるいで用いた素数候補を管理する配列に少し手を加えただけです．
エラトステネスのふるいでは，ある数\(i\)が素数であるか否かの情報だけを記録していました．
それに対し，osa_k法の前処理ではある数\(i\)の最小の素因数を記録しています．
どちらの場合もやることはほとんど変わらないため，osa_k法の前処理の計算量はエラトステネスのふるいと同じ\(O(N \log \log N)\)となります．
osa_k法の本計算の計算量は，ある数\(M\)を素因数分解するときの計算量です．本計算での操作回数は\(M\)の素因数の個数に比例します．
\(M\)の素因数の個数は\(O(\log M)\)程度ですから，計算量も\(O(\log M)\)です．
\(M\)が最大の場合（\(M==N\)の場合）も，計算量は\(O(\log N)\)です．
osa_k法であれば，\(N\)以下の正の整数全てを素因数分解する場合も計算量は\(O(N \log N)\)程度となります．
osa_k法をC++で実装
上記のコードは，osa_k法をC++で実装した例です．配列min_factorは，素数候補を管理する配列兼ある数の最小の素因数を記録する配列です．
配列min_factorにはある数の最小の素因数が記録されているため，factor関数の戻り値（素因数を記録した配列）には素因数が小さい順に格納されます．