javascript - 在 Javascript : Fails only if argument is prime 中通过埃拉托色尼筛法求和素数

Question

我的筛法本身似乎运行良好，只要最后一个值本身不是质数，求和函数就会返回正确的结果。奇怪的是，如果我直接返回它，我可以看到在 true/false 数组中适本地记录了素数，但我似乎无法为了求和的目的而真正得到它。结果，在 10 上运行此 Sieve 返回 17(正确)，但在 37 上运行它返回 160 而不是 197。在 5 上运行它返回 5 而不是 10，等等。

function sumPrimes(n) {
  var primArr = [];
  var primSum = 0;
  for (var i = 2; i < n; i++) {
    primArr[i] = true;
  }

  //sieve

  for (i = 2; i * i < n; i++) {
    if (primArr[i]){
      for (var j = 0; i * i + i * j < n; j++) {
        primArr[i * i + i * j] = false;
      }
    }
  }

  for (i = 2; i <= n; i++) {
    if (primArr[i]) {
      primSum += i;
    }
  }

  return primSum;
}

Answer 1

在你所有的for循环放置条件 <= n , 因为你想考虑 n本身也是如此。

请注意，如果将中间部分更改为这样可以节省一些计算:

for (var i = 2, sqrtN = Math.sqrt(n); i <= sqrtN; i++) {
    if (primArr[i]){
        for (var j = i * i; j <= n; j += i) {
            primArr[j] = false;
        }
    }
}