language-agnostic - 無限の素数を数える方法

Question

わかりましたので、この質問をあまり縮めるべきではなかったかもしれません...最初の 10000 個の素数を見つけるための最も効率的な方法に関する投稿を見ました。私はすべての可能な方法を探しています。目標は、素数性テストのワンストップショップを用意することです。素数を見つけるために人々が知っているすべてのテストを歓迎します。

など：

素数を見つけるさまざまな方法は何ですか?

score 3 · Accepted Answer

一部の素数検定は特定の数でのみ機能します。たとえば、Lucas-Lehmer検定はメルセンヌ数でのみ機能します。

大きな数に使用されるほとんどの素数テストは、特定の数が「おそらく素数」である (または、その数がテストに失敗した場合、それは間違いなく素数ではない) ことだけを教えてくれます。通常、数値が素数である可能性が非常に高くなるまで、アルゴリズムを続行できます。

このページ、特に「関連項目」セクションをご覧ください。

Miller-Rabin 検定は、最良の検定の1 つだと思います。標準形式では、素数の可能性が高くなりますが、3.4*10^14 未満の数値にテストを適用すると、各パラメーター 2、3、5、7、11、13 のテストに合格することが示されています。と 17 は間違いなく素数です。

AKS テストは、最初の決定論的で実証済みの一般的な多項式時間テストでした。ただし、私の知る限りでは、入力がとてつもなく大きい場合を除き、最良の実装は他のテストよりも遅くなることがわかりました。

score 2 · Accepted Answer

@akdomの私への質問：

ループは私の以前の提案でうまく機能し、数値が偶数であるかどうかを判断するために計算を行う必要はありません。ループでは、以下に示すように、すべての偶数をスキップします。

//Assuming theInteger is the number to be tested for primality.
// Check if theInteger is divisible by 2.  If not, run this loop.
//  This loop skips all even numbers.
for( int i = 3; i < sqrt(theInteger); i + 2) 
{
    if( theInteger % i == 0) 
    {
       //getting here denotes that theInteger is not prime 
       // somehow indicate that some number, i, divides it and break
       break;
    }
}

score 2 · Accepted Answer

Rutgers 大学院生が最近、素数を生成する再帰関係を発見しました。連続する数の差は、素数または 1 のいずれかを生成します。

a(1) = 7
a(n) = a(n-1) + gcd(n,a(n-1)).

それは、フィルタリングする必要がある多くのがらくたを作ります。Benoit Cloitre には、同様のタスクを実行する次の再発もあります。

b(1) = 1
b(n) = b(n-1) + lcm(n,b(n-1))

次に、連続する数の比から 1 を引いた [b(n)/b(n-1)-1] が素数です。このすべての完全な説明はRecursivityで読むことができます。

ふるいについては、ホイールを毎回追加するのではなく、ホイールを使用することでより良い結果が得られます。改善されたインクリメンタル素数ふるいを確認してください。これは車輪の例です。無視する数字 2 と 5 を見てみましょう。彼らの車輪は [2,4,2,2] です。

score 2 · Accepted Answer

エラトステネスのふるいはまともなアルゴリズムです。

正の整数 2 のリストを任意の Ceiling に取ります。

リストの次の項目 (最初の反復では 2) を取得し、その倍数 (最初の項目を超える) をすべてリストから削除します。

指定された上限に到達するまで、ステップ 2 を繰り返します。

あなたのリストは素数だけで構成されています。

このアルゴリズムには、速度をメモリと交換するという機能上の制限があります。素数の非常に大きなリストを生成するとき、必要なメモリ容量は急増しました。

score 2 · Accepted Answer

特定の整数について、私が知っている最速の素数チェックは次のとおりです。

整数の平方根に 2 のリストをとります。

リストをループして、整数/現在の数値の残りを取ります

リスト内の任意の数値の剰余がゼロの場合、その整数は素数ではありません。

リスト内のすべての数値の剰余がゼロでない場合、その整数は素数です。

The Sieve of Eratosthenesよりもメモリ使用量が大幅に少なく、個々の数値については一般的に高速です。

score 0 · Accepted Answer

2 から整数の根までのリストを使用するアルゴリズムでは、2 より後の奇数のみをテストすることでパフォーマンスを向上させることができます。つまり、リストには 2 と、3 から整数の平方根までのすべての奇数のみを含める必要があります。 . これにより、複雑さを増すことなく、ループの回数を半分に減らすことができます。

score 0 · Accepted Answer

@theprise

インスタンス化されたリストの代わりにインクリメントループを使用したい場合 (膨大な数のメモリの問題...)、リストを作成せずにそれを行うにはどうすればよいでしょうか?

通常の数 (N % X) のチェックよりも、与えられた整数 (X % 3) の割り切れるチェックを行う方が安上がりとは思えません。

score -1 · Accepted Answer

-1

素数を生成する方法を見つけたい場合は、前の質問で説明しました。

于 2008-08-10T22:47:08.340 に答える

language-agnostic - 無限の素数を数える方法

8 に答える 8

Related

Reference