c - unsigned long long 整数ですべての素因数を見つける方法は?

Question

ある数値のすべての素因数を見つけるという課題があります...

数値を受け取り、その数値のすべての素因数を教えてくれる関数を作成する必要があります。例えば：

• n=350 素因数:2 5 5 7

(0 から 18446744073709551615 の範囲の数値を関数に渡します。最大数は、64 ビットの unsigned long long 整数に収まる最大の数値です。)

Answer 1

これは難しい問題であり、量子コンピューターに関するすべての研究の主な理由の 1 つです。Shorのアルゴリズムを見てください。この特定のケース (64 ビット整数) では、実行時間をわずか数分に短縮できるはずですが、最適化を行わない単純なブルート フォースは 1000 年ほどかかります。

(せいぜい) 1 つの大きな素因数の些細なケースがあると仮定すると、2 からカウントアップして各数値を試すようなことを行うことで大幅に高速化できます (機能する場合は複数回; 12 は 2、2、および 3 になります)。例）。因数を見つけたら、その因数でターゲット数を減らし、新しいターゲットが素数であるかどうかをテストします。

さらに高速化するには、複数のスレッドで処理を行い、それぞれが一定範囲の除数を担当します。素数テスターを 1 つ以上のスレッドで実行して、素数をテスト スレッドに提供することで、素数で除算するだけで済みます。

値を提供する人が巧妙にしようとしていると思われる場合は、範囲の上から下に検索することもできますが、素数の密度が下端で非常に高いため、これはおそらく役に立ちません.

ただし、X 自体を除いて、X の可能な最大因数は X の平方根であることに注意してください。因数を見つけるたびに、残りの可能な最大因数は大幅に減少します。