0 
var fs = require('fs');
var outfile = "primes.txt";
function getPrimes(max) {
    var primeSieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!primeSieve[i]) {
            // i has not been marked - it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                primeSieve[j] = true;
            }
        }
    }
    return primes;
}
fs.writeFileSync(outfile,  getPrimes(1000).slice(0,100) + ",");
console.log("Script: " + __filename + "\nWrote: " + getPrimes(1000).slice(0,100) + "To: " + outfile);

我有上面的一段代码，我修改它以产生输出（由其他人提供的主要算法）。我是 Javascript 新手，不确定以下行实际上在做什么以及 << 运算符的含义（我无法在 Javascript 网站上找到）。

for (j = i << 1; j <= max; j += i)

我知道它将主 primeSieve 数组中的相关数字标记为真，这样它们就不会填充素数数组，但是我不知道它是如何做到的。

4

1 回答 1

1

<<运算符是左移运算符。left 参数（如果需要，在转换为整数值之后）向左移动由 right 参数指定的位数，右填充零。左移 1 与乘以 2 相同。

内部循环只是将true每个元素存储在primeSieve一个索引处，该索引是 的倍数i。因此，如果primeSieve[j]是true，则j必须是某个先前的倍数i（因此j不能是素数）。相反，如果primeSieve[i]不是true，那么它不是任何先前值的倍数i；因为这包括从2到的所有整数i-1，所以i必须是素数。

对于收集到某个最大值的所有素数，这种方法远远优于独立测试每个整数的素数的技术。然而，它远非最有效的方法。例如，请注意，一个元素primeSieve可能会被设置为true多次。例如，primeSieve[6]设置 wheni==2和 when i==3。此外，一旦i超过 的平方根max，内部循环就是一种浪费，因为直到 的所有合数max都保证在该点被标记。请参阅有关Eratosthenes 筛的 Wikipedia 文章，了解有关这一切如何工作的更多信息以及指向更有效方法的指针。

PS 该代码看起来非常熟悉。:-)

于 2013-06-23T02:24:38.693 回答