產生前 N 個質數的最優雅的方法是什麼？

優雅產生質數的方法

目標是寫一個函數 generatePrimes(n)，回傳前 n 個質數。有多種方法可以實現此功能，各有優劣。本文探討最優雅的方法。

最初的方法通常使用巢狀循環來檢查質數。雖然這種方法有效，但由於其重複性和嵌套結構，缺乏優雅性。更巧妙的方法是使用埃拉托斯特尼篩法，其時間複雜度為 O(n log log n)。

埃拉托斯特尼篩法的工作原理是創建一個大小為 n 的布林數組，所有元素最初都設為 true。數組索引表示從 0 到 n-1 的數字。演算法首先將索引 0 和 1 處的元素設為 false，因為它們不是質數。然後，對於每個索引 i，它將數組中 i 的所有倍數設為 false。這個過程對所有索引重複，直到 n 的平方根。數組中剩餘的 true 元素表示素數。

以下是埃拉托斯特尼篩法的一種優雅的 Java 實作：

<code class="language-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;
}</code>

這段程式碼使用埃拉托斯特尼篩法高效且優雅地產生了前 n 個素數。時間複雜度為 O(n log log n)，程式碼簡潔明了，是產生質數的理想選擇。

以上是產生前 N 個質數的最優雅的方法是什麼？的詳細內容。更多資訊請關注PHP中文網其他相關文章！