javascript - Javascript 中的埃拉托色尼筛法？

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);