javascript - 你能解释一下这种在 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;以及真正发生的事情。

需要明确的是..素数是只能被自身或被一整除的东西。

Answer 1

它叫做 Sieve of Erathestenes这是一种查找零到某个上限整数之间的所有素数的有效方法。

j = i << 1

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

我不认为您展示的实现是最佳的。 i 值的限制可以更低——类似于 sqrt(max)。

您可以轻松地在网上找到一些关于此算法的非常好的动画，它们以非常直观的方式向您展示正在发生的事情。