6 
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;
}

我知道它i会跟踪所有数字。

我不明白... !sieve[i]，j = i << 1;以及真正发生的事情。

只是要清楚..素数是只能被自身或被一整除的东西。

4

2 回答 2

5

它被称为Erathestenes 筛，它是一种查找零到某个上限整数之间的所有素数的有效方法。

j = i << 1

这是一个位移操作。它将整数向左移动 1 位。因为二进制是以二为底的，所以这相当于乘以二。在十进制中，等效的操作是1向左移动并在右边带入零。它是以十为底，所以你最终得到10（十乘以一）。

我不相信您展示的实现是最佳的。该i值的限制可以更低——例如sqrt(max).

你可以很容易地在网上找到一些非常漂亮的关于这个算法的动画，它们以一种非常直观的方式向你展示正在发生的事情。

于 2013-06-23T20:57:20.497 回答
4

它使用埃拉托色尼筛。

来自维基百科（http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）

素数是一个自然数，它恰好有两个不同的自然数除数：1 和它自己。

通过 Eratosthenes 的方法找到小于或等于给定整数 n 的所有素数：

  • 创建一个从 2 到 n 的连续整数列表：(2, 3, 4, ..., n)。
  • 最初，让 p 等于 2，即第一个素数。
  • 从 p 开始，以 p 为增量向上计数，并在列表中标记每个大于 p 本身的数字。这些将是 p 的倍数：2p、3p、4p 等；请注意，其中一些可能已经被标记。
  • 在未标记的列表中找到第一个大于 p 的数字。如果没有这样的号码，请停止。否则，现在让 p 等于这个数（即下一个素数），然后从步骤 3 开始重复。

当算法终止时，列表中所有未标记的数字都是素数。这里的主要思想是 p 的每个值都是素数，因为我们已经标记了所有小于 p 的数字的倍数。

于 2013-06-23T20:58:42.737 回答