使用埃拉托色尼筛法的素数和找不到错误

Question

我在 JavaScript 工作，这有点令人困惑，因为代码返回了正确的素数和。它正在处理更大的数字。有一个错误，其中 977 是 returns 976 的质数总和，即 72179，而不是 977 的总和，即 73156。到目前为止，我测试的所有内容都正确返回。

function sumPrimes(num) {

    var sum = 0;
    var count = 0;
    var array = [];
    var upperLimit = Math.sqrt(num);
    var output = [];

    for (var i = 0; i < num; i++) {
        array.push(true);
    }

    for (var j = 2; j <= upperLimit; j++) {
        if (array[j]) {
            for (var h = j * j; h < num; h += j) {
                array[h] = false;
            }
        }
    }

    for (var k = 2; k < num; k++) {
        if (array[k]) {
            output.push(k);
        }
    }

    for (var a = 0; a < output.length; a++) {
        sum += output[a];
        count++;
    }

    return sum;
}

sumPrimes(977);

Answer 1

问题是因为你的 "seive" Array 是从 0 开始索引的，但是你的算法假定 array[n] 代表数字 n.

由于您希望 array[n]===true 表示 n 是素数，因此如果您希望最后一项被索引为 Array，则需要长度 978 =17=] 和表示数字 977.

当我将 < num 的所有实例更改为 < num+1 时，问题似乎已解决。

使用埃拉托色尼筛法的素数和找不到错误

Sum of Primes using Sieve of Eratosthenes can't find bug

javascript

primes

sum

sieve-of-eratosthenes