素数を効率的に生成するにはどうすればよいでしょうか?

優雅かつ効率的に素数を生成する

プログラミングの分野では、素数を生成するエレガントで効率的な方法を見つけるのは古典的なことです。チャレンジ。簡潔さとパフォーマンスのバランスを取るアプローチを検討してみましょう。

n 以下の素数の数を pi(n) ≈ n / log(n) として推定する素数定理の使用を考えてみましょう。 。この推定値は、素数を識別するために使用できるふるいのサイズの上限を提供します。

エラトステネスの篩としても知られるふるい法は、数値の範囲を反復処理し、数値以外のものをすべて除去します。それらを複合としてマークしてプライムします。このタスクでは、BitSet を利用して素数のセットを表し、各ビットが範囲内の数値に対応します。

以下は、この洗練された効率的な素数生成メソッドの Java 実装です。

<code class="java">public static BitSet computePrimes(int limit) {
    BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j < limit; j += i) {
                primes.clear(j);
            }
        }
    }
    return primes;
}</code>

この方法は、一般的なラップトップで最初の 100 万個の素数を約 1 秒で効率的に生成します。精度と速度の組み合わせにより、さまざまなコンピューティング シナリオで素数を生成するための貴重なツールとなります。

以上が素数を効率的に生成するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。