本当に大きい (long long の範囲内の) 数値間の間隔で素数性をテストする必要があるため、数値が素数かどうかを確認するための高速なアルゴリズムが必要です。あなたのアイデアを提案してください。
37828 次
10 に答える
19
良い方法の 1 つは、Miller-Rabin検定です。ただし、これは確率論的なテストにすぎないことに注意してください。
于 2010-04-06T16:47:24.837 に答える
10
漸近的に最速の現在の (非確率論的) 素数性テストは、本質的に O(n^6) の複雑さを持つ "Lenstra/Pomerance 改良 AKS" であると思います。
ただし、long long(64 ビット整数である典型的なシステムを想定して) の範囲は実際にはそれほど大きくありません。特に、2^32 未満の素数は約 2 億個しかないため、高速な確率テストを使用して、事前に計算された素数のリストを使用して試行分割を行います (または素数のリストがある場合は、その数を調べます)。 ) は、その範囲では非常に高速であり、おそらく正しい方法です。
于 2010-04-06T16:53:45.563 に答える
7
Miller-Rabinアルゴリズムを使用するGNU MP ライブラリをお勧めします。私はそれを数ヶ月間使用しましたが、非常に高速です。
具体的には、関数 mpz_probab_prime_p がこれを行います。別の関数 mpz_nextprime を使用して、数値より大きい次の素数を見つけることもできます。必要に応じて、コード サンプルを投稿できます。
于 2010-04-06T16:55:59.587 に答える
5
long long の素数性をテストする場合は、ベイリー PSW 素数性テストが適しています。このテストは、1 つの強力な疑似素数テストと 1 つの Lucas テストを実行するため、非常に高速です。このテストに合格する複合材料がいくつか存在すると予想されますが、これまでのところ知られていないものはなく、10 15未満の例外はありません。このテストの変形は、たとえば Mathematica で使用されます。
于 2010-04-06T21:14:14.737 に答える
5
私は非常に優れたアルゴリズムを思いつきました。これは、すべての除数をチェックするよりもはるかに高速です。もちろん、公開鍵暗号をクラックすることもできます。
待ってください - 窓を閉める必要があります。頭上にはこれらの黒いヘリコプターがすべてあります........
(または素数性をテストするにはどうすればよいですか? を参照してください)
于 2010-04-06T16:46:58.540 に答える
1
ここで私の答えを見てください：
テストは非常に高速です。64 ビット以下の範囲で作業している場合は、30030 で GCD を投入して、ほとんどの数値の時間を少し節約できます。
于 2010-04-06T17:03:01.480 に答える
1
コバルとグロクスは正しい。Miller-Rabin 検定は、利用可能なアルゴリズムの中で最も有用です。はい、それは確率論的ですが、実際にあなたを怖がらせるべきではありません. テストは、実用的な目的で最も広く使用されています。
テストを繰り返すことで、偽陽性 (偽陰性がない) の確率を任意に小さくできることに注意してください。
于 2010-04-06T17:00:19.867 に答える
-1
私の見解では、最良のアルゴリズムは「ALI primality test」です。
于 2013-08-06T18:36:41.987 に答える
-3
おそらく、事前に計算された素数のリストで検索するのが最も速いでしょう。たとえば、こちらを参照してください。最大 2^43112609-1 (知られている最大の素数) です。
于 2010-04-06T16:49:02.983 に答える