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

Question

我在 JavaScript 中工作，这有点令人困惑，因为代码返回了正确的素数和。它正在处理更大的数字。有一个错误，对于 977，它返回 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如果您希望最后一项被索引为 array[977]并且意味着数字977 .

当我更改 < num 的所有实例时，问题似乎得到解决至 < num+1 .