最初の N 個の素数を生成する最もエレガントな方法は何ですか?

素数を生成するエレガントな方法

目標は、最初の generatePrimes(n) 素数を返す関数 n を作成することです。この機能を実現するには複数の方法があり、それぞれに長所と短所があります。この記事では、最もエレガントな方法について説明します。

元のアプローチでは通常、ネストされたループを使用して素数をチェックします。このアプローチは機能しますが、反復的で入れ子になった構造のため、優雅さに欠けます。より洗練されたアプローチは、時間計算量が O(n log log n) のエラトステネスのふるいを使用することです。

エラトステネスのふるいは、すべての要素が最初に true に設定された、サイズ n のブール配列を作成することによって機能します。配列インデックスは 0 から n-1 までの数値を表します。アルゴリズムは、インデックス 0 と 1 の要素が素数ではないため、最初に false に設定します。次に、インデックス i ごとに、配列内の i の倍数をすべて false に設定します。このプロセスは、n の平方根までのすべてのインデックスに対して繰り返されます。配列内の残りの true 要素は素数を表します。

以下は、エラトステネスの篩のエレガントな Java 実装です:

public static List<Integer> generatePrimes(int n) {
    if (n <= 0) {
        return new ArrayList<>();
    }
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }
    return primes;
}

このコードは、エラトステネスのふるいを使用して、最初の n 素数を効率的かつエレガントに生成します。時間計算量は O(n log log n) で、コードは簡潔かつ明確で、素数の生成に最適です。

以上が最初の N 個の素数を生成する最もエレガントな方法は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。