Java でエラトステネスのふるいを使用して素数をエレガントに生成するにはどうすればよいですか?

Java のエラトステネスのふるい: 素数をエレガントに生成します

はじめに

素数の生成はコンピューター サイエンスの基本的な問題であり、さまざまなアルゴリズムから選択できます。中でもエラトステネスのふるいは、そのシンプルさと効率性で知られています。この記事では、エラトステネスのふるいを使用して最初の n 個の素数を生成するエレガントな Java 実装を提供します。

エラトステネスの篩

エラトステネスの篩は、素数の倍数を繰り返し排除することで素数を特定する確率的アルゴリズムです。まず、ブール型フラグの配列を初期化します。各フラグは、指定された制限までの数値を表します。次に、アルゴリズムは最初の素数 2 から始まる配列を反復処理し、そのすべての倍数を非素数としてマークします。このプロセスは、制限内のすべての数値が削除され、素数だけが残るまで続けられます。

エレガントな実装

エラトステネスの篩のエレガントな Java 実装は次のようになります:

public static BitSet computePrimes(int limit) {
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 2; i * i <= limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j <= limit; j += i) {
                primes.set(j, false);
            }
        }
    }
    return primes;
}

説明

この実装は、各ビットが指定された制限までの数値を表す BitSet を作成します。最初は、0 と 1 は非素数としてマークされ、他のすべての数値は素数としてマークされます。

外側のループは、最初の素数 2 から始めて配列を繰り返します。現在の位置のビットが設定されている (素数であることを示している) 場合、内側のループはその素数のすべての倍数を非素数としてマークします。このプロセスは、制限内のすべての数値が排除されるまで続きます。

最後に、素数を含む BitSet を返します。

結論

このエラトステネスの篩の Java 実装は、アルゴリズムの優雅さと単純さを示しています。素数を効率的に生成し、明確な論理構造を備えています。このコードはパフォーマンスと理解しやすさを考慮して最適化されており、素数ジェネレーターを必要とするプログラマーにとって貴重なツールとなっています。

以上がJava でエラトステネスのふるいを使用して素数をエレガントに生成するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。