[解決済み] 数の素因数分解の最大値を求めるアルゴリズム

質問

ある数の最大の素因数を計算するには、どのような方法があるか？

最も効率的なのは次のようなものだろうと考えています。

1. きれいに割り切れる最も小さい素数を探す
2. 割り算の結果が素数かどうかのチェック
3. そうでない場合、次に低いものを探す
4. 2に進みます。

素因数が小さい方が計算しやすいという前提で考えています。この程度でよいのでしょうか？また、他にどのようなアプローチをとればよいでしょうか？

編集：今気づいたのですが、素因数が2つ以上ある場合、私のアプローチは無駄です。なぜなら、結果が他の2つの素数の積である場合、ステップ2は失敗するので、再帰的アルゴリズムが必要だからです。

再度編集します。なぜなら、最後に見つかった素数は最も大きいものでなければならないからです。したがって、ステップ2の素数でない結果をさらに検証すると、より小さい素数が得られることになります。

解決するには？

実は、大きな数の因数を求めるには、もっと効率的な方法がいくつかあります（小さな数の場合は、割り算の試行がそれなりに有効です）。

入力された数が平方根に非常に近い2つの因子を持つ場合、非常に高速な方法の1つは、次のように知られています。 フェルマー因数分解 . これは恒等式 N = (a + b)(a - b) = a^2 - b^2 を利用したもので、理解も実装も簡単です。残念ながら、一般にあまり高速ではありません。

長さ100桁までの数の因数分解で最もよく知られている方法は 二次ふるい . おまけに、このアルゴリズムの一部は、並列処理で簡単にできる。

さらにもう一つ、私が聞いたことのあるアルゴリズムが ポラードのRhoアルゴリズム . 一般に二次ふるいほど効率的ではありませんが、実装はより簡単なようです。

数を2つの因数に分割する方法が決まったら、私が思いつく限り、数の最大の素因数を求める最速のアルゴリズムを紹介します。

最初に数そのものを格納する優先キューを作成する。繰り返しごとに、キューから最も大きい数を取り出し、それを2つの因子に分割しようとする（もちろん、その因子の1つに1は許されない）。このステップに失敗した場合、その数は素数であり、答えが得られたことになります。そうでない場合は、2つの因子を行列に追加し、繰り返します。