如何有效地找到给定范围内的素数？

在给定范围内查找素数

在数学中，素数是大于 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中文网其他相关文章！