CODEWITHSUNDEEP
javascriptalgorithmsieve-of-eratosthenes
Vincent Chee
Vincent Chee

Reputation: 45

Why is this implementation of Sieve of Eratosthenes incorrect?

The goal is to find the sum of all primes up till num. I've seen the same implementation on another post, but it also doesn't work: Sieve of Eratosthenes algorithm in JavaScript running endless for large number

However, the solution there is also incorrect when I try it with 977, it returns 72179, but it should be 73156. 

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;
};

Pseudocode obtained from: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Upvotes: 1

Views: 209

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58320

There's nothing wrong with your code. It returns the sum of primes less than num, and the sum of primes less than 977 is 72179. Your expected answer of 73156 is the sum of primes less than or equal to 977. The difference is 977 because 977 is prime.

Upvotes: 3

Related Questions