你能解释一下这种在 javascript 中寻找素数的方法吗？

Question

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;以及真正发生了什么。

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

Answer 1

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

j = i << 1

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

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

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

Answer 2

它使用埃拉托斯特尼筛法。

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

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

通过埃拉托色尼方法查找所有小于或等于给定整数 n 的素数：

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

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