JavaScript中的Eratosthenes筛选器？

Question

所以我想这个伪代码从Wikipedia翻译成JavaScript：

Input: an integer n > 1 

Let A be an array of Boolean values, indexed by integers 2 to n, 
initially all set to true. 

for i = 2, 3, 4, ..., not exceeding √n: 
    if A[i] is true: 
    for j = i^2, i^2+i, i^2+2i, i^2+3i, ..., not exceeding n : 
     A[j] := false 

Output: all i such that A[i] is true. 

这是据我得到：

function getPrimes(num) { 
    var a = []; 
    for (i=2;i<=num;i++){a.push(true);} 
    for (i=2;i<=Math.sqrt(num);i++){ 
    for (var j=i*i, coef=0, l=i;j<num-2;coef++){ 
     j = i*i+coef*l-2; 
     a[j]=false; 
    } 
    for (i=0;i<a.length;i++){ 
     if (a[i]){a.splice(i,1,i+2);} 
    } 
    } 
    return a; 
} 

getPrimes(10); // returns [2, 3, false, 5, false, 7, false, 9, false] 
       // 9 should be false 

因此，大家可以看到，该算法不捕获所有非素数。任何想法，我已经错过了？预先感谢任何想尝试它的人。

Answer 1

您正在覆盖外循环的i变量，第二个内循环也使用i。所以外层循环只运行一次。

使用内部循环的另一个变量，如k，你会得到一个很好的结果。

但是没有必要让那个特定的内环定位在那里。它只需要在返回之前运行一次。所以你可以将它移出主循环。

一个小问题是，你的第一内环走得太远，因为j在循环的身体得到递增，并在j测试只有您已经指定了价值a[j]后会发生。 JavaScript只是创建那个元素，使阵列更长，但它会更好，如果你会阻止这种情况发生

我也会保留数组a的前2个索引代表数字0和1，只是为了让您的代码更具可读性：那么您不再需要那些+2和-2。

考虑到所有这些因素，再加上一些其他的优化，我建议这个ES6代码：

function getPrimes(num) { 
 
    var a = [...Array(num+1).keys()]; // =[0,1,...,num] 
 
    a[1] = 0; // 1 is not prime 
 
    var rt = Math.sqrt(num); // calculate only once 
 
    for (i=2;i<=rt;i++){ 
 
    for (var j=i*i; j<=num; j+=i) a[j]=0; 
 
    } 
 
    return a.filter(Number); // kick out the zeroes 
 
} 
 
// run it for 30 
 
var a = getPrimes(30); 
 
// Output 
 
console.log(a);