在 Javascript 中通过埃拉托色尼筛法对素数求和：仅当参数为素数时失败

Question

我的筛法本身似乎运行良好，只要最后一个值本身不是素数，求和函数 return 就是正确的结果。奇怪的是，如果我直接 return 它，我可以看到在 true/false 数组中适当地记录了素数，但我似乎无法为了求和的目的而真正得到它。结果，运行这个 Sieve 在 10 returns 17（正确），但是运行它在 37 returns 160 而不是 197。运行它在 5 returns 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;
        }
    }
}

在 Javascript 中通过埃拉托色尼筛法对素数求和：仅当参数为素数时失败

Sum primes via Sieve of Eratosthenes in Javascript: Fails only if argument is prime

javascript

algorithm

primes