素数生成におけるエラトステネスのふるいはどのくらい効率的ですか?

最もエレガントな素数生成: ふるいアプローチ

素数を生成するという課題に直面したとき、コードのエレガントさを追求することは崇高な追求です。素数を見つける方法は数多くありますが、エラトステネスのふるいはそのシンプルさと効率性で際立っています。

エラトステネスのふるいは、1 から n までの数値を表す長さ n のブール配列を作成することによって機能します。配列は最初、すべての要素に対して true に設定され、各数値が素数になる可能性があることを示します。次にアルゴリズムは、マークされていない最初の数値 2 から開始して配列を反復処理します。配列内の値を false に設定することで、2 の倍数すべてを非素数としてマークします。次に、次のマークされていない数値 3 に移動し、このプロセスを繰り返し、すべての 3 の倍数を非素数としてマークします。これは最後のマークされていない数値 √(n) まで続きます。

このアプローチを使用することにより、エラトステネスのふるいは素数を見つけるために必要なチェックの数を大幅に減らし、非常に効率的なソリューションを提供します。次の Sieve の 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>

このコードは、1 から n までの数値を表す BitSet を作成し、すべての要素を最初に true に設定します。次に、配列を反復処理して、各素数 (2 から始まる) のすべての倍数を非素数としてマークします。結果は、true に設定された要素のみが素数を表す BitSet になります。

以上が素数生成におけるエラトステネスのふるいはどのくらい効率的ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。