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

Javascript 中的埃拉托色尼筛法？

Sieve of Eratosthenes in Javascript?

javascript

arrays

scope

for-loop

sieve-of-eratosthenes