符号なしlong long整数のすべての素因数を見つけるには？

Question

私は、数値のすべての素因数を見つけるための割り当てを持っています...

私は数を取る関数を書く必要があり、数のすべての素因数を教えてください。

• N = 350素因数：例えば2 5 7

（Iは範囲0 18446744073709551615に関数に数値を渡す - 最大数に収まる最大数であります64ビットの符号なしlong long整数）

Answer 1

これは難しい問題であり、量子コンピュータのすべての研究の主な理由の1つです。 Shor's Algorithmをご覧ください。最適化を行わない単純なブルートフォースは1000年のようなものですが、この特定のケース（64ビット整数）では実行時間をわずか数分に短縮できるはずです。

1つの大きな素因数をとることが少ないと仮定すると、2からカウントアップして各数値を試してみると、スピードアップが大幅に向上します（動作する場合は複数回、2の場合は12回、3など）。因子を見つけたら、その因子で標的数を減らし、新しい標的が素数であるかどうかをテストします。

さらに高速化するために、複数のスレッドにわたって処理を行い、各スレッドはそれぞれの除数の範囲を担当します。素数を1つ以上のスレッドで実行し、素数をテストスレッドに提供して、素数でしか割り切れないようにすることができます。

値を提供している人物がトリックであると思っている場合は、範囲の上から検索することもできますが、下位のプライムの密度がそれほど高くない場合、助けて。

Xの最大可能因数は、X自体のほかにXの平方根です。因子を見つけるたびに、可能な限り大きな残りの因子が大幅に減少します。