-1

n ≤ 10¹⁸ の場合、n より小さい最大の素数を見つけるにはどうすればよいですか? 効率的なアルゴリズムを見つけるのを手伝ってください。

for(j=n;j>=2;j--) {
  if(j%2 == 1) {
    double m = double(j);
    double a = (m-1)/6.0;
    double b = (m-5)/6.0;
    if( a-(int)a == 0 || b-(int)b == 0 ) {
      printf("%llu\n",j);
      break;
    }
  }
}

私はこのアプローチを使用しましたが、これは n>10^10 を解決するのに効率的ではありません。

これを最適化する方法..

編集: 解決策: 各 j で素数テストを使用します。

ミラー・ラビン、フェルマーのテスト。

4

1 に答える 1

7

この範囲の数値の効率を判断するのはそれほど簡単ではないため、この質問をすぐに却下すべきではないと思います。まず第一に、素数ギャップの平均がであるとすると、与えられた から下ln(p)に作業することは理にかなっています。つまり、から平均して反復回数が減少することが予想されます。例：テスト：(n)ln(10^18) ~ 41.44)41(n)(n), (n - 2), (n - 4), ...

この平均ギャップを考慮して、次のステップは単純なテストを使用するかどうかを決定することです<= floor(sqrt(n))。ではn <= (10^18)、素数に対してテストする必要があります<= (10^9)。この範囲には~ 5000 万の素数があります。これらの値 (すべて 32 ビットに収まる) を事前に計算して集計する場合は、64 ビット値について妥当なテストを行うことができますn <= 10^18。この場合、200MB の主要なテーブルは受け入れられるアプローチですか? 20年前なら、そうでもなかったかもしれません。今日、それは問題ではありません。

素数表とふるい分けおよび/またはポックリントン検定を組み合わせると、効率が向上する可能性があります。または、メモリがより制約されている場合は、基数を使用したMiller-Rabin テストの決定論的バリアント: 2, 325, 9375, 28178, 450775, 9780504, 1795265022 (SPRP set) . ほとんどのコンポジットは、SPRP-2 テストですぐに失敗します。

ポイントは、アルゴリズムの複雑さ、理論的および実装の難しさの両方と、空間/時間のトレードオフとのバランスの間で決定を下す必要があるということです。

于 2013-05-04T15:38:53.890 に答える