如何有效地找到給定範圍內的質數？

在給定範圍內查找素數

在數學中，素數是大於1 的整數，除了1 和它們本身之外，不能被任何其他數字整除。尋找特定範圍內的質數可能是常見的程式設計任務。以下是如何在 JavaScript 中解決此問題的詳細說明：

暴力方法

提供的程式碼片段嘗試使用暴力方法來尋找 0 到 100 之間的素數。它檢查該數字是否可以被 2 到 12 之間的任何數字整除，如果找不到約數則傳回該數字。然而，這種方法有幾個缺點：

• 效率低下，尤其是對於較大的範圍。
• 很難擴展以找到更大範圍的素數。

埃拉托斯特尼篩法

一種更有效的查找素數的演算法稱為埃拉托斯特尼篩法。它的工作原理如下：

1. 建立一個名為 sieve 的數組，長度最大為 1。
2. 將陣列中的所有元素初始化為 false（假設 false 表示該數字是質數）。
3. 從 2 到 max 的平方根迭代篩子數組。
4. 對於每個素數 i，透過設定 sieve[i j] 將其所有倍數標記為非素數對於從 i j 到 max 的所有 j 為 true。
5. 迭代後，篩數組中未標記的數字是素數。

在JavaScript 中，程式碼為埃拉托斯特尼篩法看起來像這樣：

<code class="js">function getPrimes(max) {
    var sieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!sieve[i]) {
            // i has not been marked -- it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                sieve[j] = true;
            }
        }
    }
    return primes;
}</code>

這種方法的時間複雜度為O(n log log n)，比蠻力方法有效率得多。

以上是如何有效地找到給定範圍內的質數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！