代码之家  ›  专栏  ›  技术社区  ›  Vincent Chee

为什么Eratosthenes筛的这种实现不正确?

  •  1
  • Vincent Chee  · 技术社区  · 8 年前

    目标是找到所有素数的总和,直到num。我在另一篇文章中看到了相同的实现,但它也不起作用: Sieve of Eratosthenes algorithm in JavaScript running endless for large number

    const sumPrimes = num => {
        var numList = [];
        var output = [];
        for (var i = 0; i < num; i++) {
            numList.push(true);
        }
    
        for (var i = 2; i <= Math.sqrt(num); i++) {
            if (numList[i]) {
                for (var j = i * i; j < num; j += i) {
                    numList[j] = false;
                }
            }
        }
    
        for (var k = 2; k < num; k++) {
            if (numList[k]) {
                output.push(k);
            }
        }
        var sum = output.reduce((acc, cur) => acc + cur, 0);
        console.log(output);
        return sum;
    };
    

    伪代码来自: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

    1 回复  |  直到 8 年前
        1
  •  3
  •   Paul Hankin    8 年前

    你的代码没有问题。它返回的素数之和小于 num ,且小于977的素数之和为72179。您的预期答案73156是素数之和小于