Problem 3

大きな数の最大素因数を求める

最初に浮かんだ方針は、

1. 素数のリストを生成
2. filter と使って「大きな数」の素因数を抽出
3. その中で最大のものを拾う

シンプルに行けると嬉しかったが、実際やってみると計算量が多すぎて一向に答えが出てこない。もうちょっと工夫をしなきゃ・・・ということで方針を変更する。

1. 「大きな数」を2で割れるだけ割る
2. 1の答えを次の素数3で割れるだけ割る
3. 2の答えを次の素数で、その答えをまた次の素数で、小さい方から順番に処理
4. 割り算の答えが素数になったら、それこそが求める答え

若干わかりにくいので「大きな数」を23,940として具体的に上の手順をやってみると

23940 / 2 = 11970
11970 / 2 = 5985
5985 / 2 → 割れない
5985 / 3 = 1995
1995 / 3 = 665
665 / 3 → 割れない
665 / 5 = 133
133 / 5 → 割れない
133 / 7 → 19
19は素数なのでこれが求める答え

最初の方法の難点は、例えば23,940に対してだったら150個以上の素数を評価しなければならないこと。対して見直し後の手順は9回の操作で済む。数が大きくなれば、この違いはもっと顕著になる。

あとは素数列の生成をどうするかという問題があるが、今回は素数の生成が計算の律速にはならないので、伝統的なアレで良しとする。

ということで全体はコチラ。

なんて言うてますけど、かなり苦戦しました★