埃拉托斯特尼篩法生成素數的效率如何？

最優雅的素數生成：篩法

當面臨生成素數的挑戰時，力求程式碼優雅是一種崇高的追求。雖然有許多查找素數的方法，但埃拉托斯特尼篩法因其簡單性和高效性而脫穎而出。

埃拉托斯特尼篩法透過建立長度為 n 的布林數組來運行，該數組表示從 1 到 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>

此程式碼建立一個 BitSet 來表示從 1 到 n 的數字，並將所有元素初始設為 true。然後它迭代數組，將每個素數（從 2 開始）的所有倍數標記為非素數。結果是一個 BitSet，其中唯一設定為 true 的元素代表質數。

以上是埃拉托斯特尼篩法生成素數的效率如何？的詳細內容。更多資訊請關注PHP中文網其他相關文章！