212

C ++を使用して素数を見つけるための最速のアルゴリズムはどれですか？私はふるいのアルゴリズムを使用しましたが、それでももっと速くしたいです！

4

18 に答える 18

92

アトキンのふるいの非常に高速な実装は、 DanBernsteinのprimegenです。このふるいはエラトステネスのふるいよりも効率的です。彼のページにはいくつかのベンチマーク情報があります。

于 2009-01-17T18:45:25.783 に答える
33

本当に高速である必要がある場合は、素数のリストを含めることができます：http:
//www.bigprimes.net/archive/prime/

特定の数が素数であるかどうかを知る必要がある場合は、ウィキペディアにさまざまな素数テストがリストされています。特に、数が素数でないかどうかを判断できるため、これらはおそらく、大きな数が素数であるかどうかを判断するための最速の方法です。

于 2009-01-17T18:48:13.797 に答える
26

彼、彼は私が古い質問に答える質問ネクロマンサーであることを知っていますが、効率的な素数テストを実装する方法をネットで検索しているときにこの質問を見つけました。

これまでのところ、最速の素数テスト アルゴリズムは SPRP (Strong Probable Prime) だと思います。Nvidia CUDA フォーラムから引用しています。

数論におけるより実用的なニッチな問題の 1 つは、素数の識別に関係しています。N が与えられた場合、それが素数かどうかを効率的に判断するにはどうすればよいでしょうか? これは単なる理論上の問題ではなく、おそらく特定の範囲内でプライム ハッシュ テーブルのサイズを動的に検出する必要がある場合に、コードで必要とされる実際の問題である可能性があります。N が 2^30 程度の場合、本当に 30000 分割テストを実行して因数を検索しますか? 明らかにそうではありません。

この問題に対する一般的な実用的な解決策は、オイラー確率素数検定と呼ばれる単純な検定と、強い確率素数 (SPRP) と呼ばれるより強力な一般化です。これは、整数 N が素数かそうでないかを確率論的に分類できるテストであり、テストを繰り返すことで正しさの確率を高めることができます。テスト自体の遅い部分は、ほとんどの場合、N を法とする A^(N-1) と同様の値を計算することです。RSA 公開鍵暗号の亜種を実装する人は誰でも、このアルゴリズムを使用しています。巨大な整数 (512 ビットなど) と通常の 32 ビットまたは 64 ビットの整数の両方に役立ちます。

テストは、N の範囲で常に成功することが知られている特定のテスト入力パラメーターを事前計算することにより、確率論的棄却から素数性の決定的な証明に変更できます。残念ながら、これらの「最もよく知られているテスト」の発見は、事実上、巨大な (実際には無限) ドメイン。1980 年に、有用なテストの最初のリストが Carl Pomerance (彼の Quadratic Seive アルゴリズムで RSA-129 を因数分解したことで有名です) によって作成されました。その後、Jaeschke は 1993 年に結果を大幅に改善しました。2004 年に、Zhang と Tang は理論を改善しました。および検索ドメインの制限。Greathouse と Livingstone は、これまでで最も最新の結果を Web で公開しました。これは、巨大な検索ドメインの最良の結果であるhttp://math.crg4.com/primes.htmlです。

詳細については、http: //primes.utm.edu/prove/prove2_3.htmlおよびhttp://forums.nvidia.com/index.php?showtopic=70483を参照してください。

非常に大きな素数を生成する方法だけが必要で、整数 n 未満のすべての素数を生成する必要がない場合は、Lucas-Lehmer 検定を使用してメルセンヌ素数を検証できます。メルセンヌ素数は 2^p -1 の形式です。Lucas-Lehmer 検定は、メルセンヌ素数に対して発見された最速のアルゴリズムだと思います。

また、最速のアルゴリズムだけでなく、最速のハードウェアも使用したい場合は、Nvidia CUDA を使用して実装し、CUDA 用のカーネルを作成して GPU で実行してみてください。

十分な数の素数を発見すれば、お金を稼ぐことさえできます。EFF は 5 万ドルから 25 万ドルの賞金を提供しています: https://www.eff.org/awards/coop

于 2011-09-26T12:57:47.330 に答える
6

あなたの問題は、特定の数が素数かどうかを判断することですか? 次に、素数テストが必要です (簡単です)。または、指定された数までのすべての素数が必要ですか? その場合、素ふるいが適しています (簡単ですが、メモリが必要です)。それとも、数の素因数が必要ですか? これには因数分解が必要になります (最も効率的な方法が本当に必要な場合は、大きな数の場合は困難です)。あなたが見ている数字はどれくらいの大きさですか？16ビット？32ビット？より大きい？

賢明で効率的な方法の 1 つは、素数の表を事前に計算し、ビットレベルのエンコーディングを使用してファイルに保存することです。ファイルは 1 つの長いビット ベクトルと見なされますが、ビット n は整数 n を表します。n が素数の場合、そのビットは 1 に設定され、それ以外の場合は 0 に設定されます。ルックアップは非常に高速で (バイト オフセットとビット マスクを計算します)、ファイルをメモリにロードする必要はありません。

于 2009-01-17T20:24:46.423 に答える
2

アプリケーションによって異なります。いくつかの考慮事項があります。

  • いくつかの素数が素数であるかどうかの情報だけが必要ですか、特定の制限までのすべての素数が必要ですか、それとも（潜在的に）すべての素数が必要ですか？
  • あなたが扱わなければならない数はどれくらいですか？

ミラーラビン素とアナログのテストは、特定のサイズ（数百万程度）を超える数のふるいよりも高速です。その下では、試行割り算（数が少ない場合）またはふるいを使用する方が高速です。

于 2009-01-17T22:37:57.840 に答える
1

Rabin-Millerは、標準的な確率的素数性テストです。(あなたはそれを K 回実行し、入力数値は間違いなく複合数であるか、おそらくエラーの確率 4 -Kで素数です。(数百回の反復で、ほぼ確実に真実を伝えています)

Rabin Millerの非確率的 (決定論的)バリアントがあります。

証明された最大の素数 (2017 年 6 月時点で 2 74,207,281 - 1) の世界記録を発見した Great Internet Mersenne Prime Search (GIMPS) は、いくつかのアルゴリズムを使用しますが、これらは特殊な形式の素数です。ただし、上記の GIMPS ページには、いくつかの一般的な決定論的素数性テストが含まれています。どのアルゴリズムが「最速」であるかは、テストする数のサイズに依存することを示しているようです。数値が 64 ビットに収まる場合は、おそらく数百万桁の素数で動作することを目的としたメソッドを使用しないでください。

于 2009-01-17T21:01:27.333 に答える
-2

私は常に、ふるいアルゴリズムに従って素数を計算するためにこの方法を使用しています。

void primelist()
 {
   for(int i = 4; i < pr; i += 2) mark[ i ] = false;
   for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
   for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
       if(mark[ i ])
          for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
  prime[ 0 ] = 2; ind = 1;
  for(int i = 3; i < pr; i += 2)
    if(mark[ i ]) ind++; printf("%d\n", ind);
 }
于 2015-08-01T11:37:25.190 に答える
-3 
#include<stdio.h>
main()
{
    long long unsigned x,y,b,z,e,r,c;
    scanf("%llu",&x);
    if(x<2)return 0;
    scanf("%llu",&y);
    if(y<x)return 0;
    if(x==2)printf("|2");
    if(x%2==0)x+=1;
    if(y%2==0)y-=1;
    for(b=x;b<=y;b+=2)
    {
        z=b;e=0;
        for(c=2;c*c<=z;c++)
        {
            if(z%c==0)e++;
            if(e>0)z=3;
        }
        if(e==0)
        {
            printf("|%llu",z);
            r+=1;
        }
    }
    printf("|\n%llu outputs...\n",r);
    scanf("%llu",&r);
}
于 2011-11-16T17:49:04.950 に答える
-4 
#include <iostream>

using namespace std;

int set [1000000];

int main (){

    for (int i=0; i<1000000; i++){
        set [i] = 0;
    }
    int set_size= 1000;
    set [set_size];
    set [0] = 2;
    set [1] = 3;
    int Ps = 0;
    int last = 2;

    cout << 2 << " " << 3 << " ";

    for (int n=1; n<10000; n++){
        int t = 0;
        Ps = (n%2)+1+(3*n);
        for (int i=0; i==i; i++){
            if (set [i] == 0) break;
            if (Ps%set[i]==0){
                t=1;
                break;
            }
        }
        if (t==0){
            cout << Ps << " ";
            set [last] = Ps;
            last++;
        }
    }
    //cout << last << endl;


    cout << endl;

    system ("pause");
    return 0;
}
于 2012-02-29T16:57:32.853 に答える
-4

少し遅いことはわかっていますが、これは検索からここにたどり着いた人々にとって役立つ可能性があります. とにかく、素因数のみをテストする必要があるという事実に依存する JavaScript を次に示します。そのため、コードによって生成された初期の素数は、後の素因数のテスト要素として再利用されます。もちろん、偶数と mod 5 の値はすべて最初に除外されます。結果は配列 P にあり、このコードは i7 PC で 1.5 秒以内に 1000 万の素数 (または約 20 秒で 1 億) を処理できます。C で書き直すと、非常に高速になるはずです。

var P = [1, 2], j, k, l = 3

for (k = 3 ; k < 10000000 ; k += 2)
{
  loop: if (++l < 5)
  {
    for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
      if (k % P[j] == 0) break loop

    P[P.length] = k
  }
  else l = 0
}
于 2014-06-26T17:32:22.043 に答える
-12 
#include<iostream>
using namespace std;

void main()
{
    int num,i,j,prime;
    cout<<"Enter the upper limit :";
    cin>>num;

    cout<<"Prime numbers till "<<num<<" are :2, ";

    for(i=3;i<=num;i++)
    {
        prime=1;
        for(j=2;j<i;j++)
        {
            if(i%j==0)
            {
                prime=0;
                break;
            }
        }

        if(prime==1)
            cout<<i<<", ";

    }
}
于 2012-03-11T17:05:52.830 に答える