Sum all primes problem sieve not working

JavaScript
1

I am having trouble finding primes. I implemented Sieve but not sure if its correct. Any help is appreciated

/*algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.
    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.    
    for i = 2, 3, 4, ..., not exceeding √n do
        if A[i] is true
            for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                A[j] := false
    return all i such that A[i] is true.
*/
function sumPrimes(num) {
  let booleanResult = [];
  let numResult = [];
  let limitsqrRoot = Math.sqrt(num);
  //initializing array
  for (let i = 0;i < num;i++){
    booleanResult.push(true);
  }
  for (let i = 1;i <= limitsqrRoot;i++){
    if (booleanResult[i]){
      for (let j = i*2;j <= num;j += i){
        booleanResult[j] = false;
      }
    }
  }
  for(let i = 2;i <= booleanResult.length;i++){
    if(booleanResult[i]){
      numResult.push(i);
    }
  }
  return numResult.reduce((total,current) => total+current);
}

console.log(sumPrimes(977));// I am getting 72179
// should be 73156
2

Hello.

I think that you need to adjust your limit to include num.

Nice work tackling a Sieve of Eratosthenes based approach!

3

Ah! You will want to start with 2 as well. I was getting an error because you marked all multiples of 1 as not prime.

4

I seem to be missing 977(last prime number). For some reason its not being included in the numResult array

5

Yeah, that’s what I meant by “adjust your limit to include num”.

6

okay thank you for your time and help, really appreciate it.

7

No problem. Nice work on the solution - it’s one of the fastest approaches to the problem on the forum.

If you are interested, there are a couple of little tweaks you can make to make it even faster!

8

Sure, I would love to improve the solution. Please guide me.

9

The only even prime number is 2. So you never need to check if any other prime number is even.

The details are a bit delicate, but you can make your array ‘booleanResult’ only track even numbers.

You can also get a little performance boost to use this array to sum instead of making and reducing the ‘numResult’ array.

The last thing you can do is somewhat ‘non JavaScripty’, but you can actually preallocate an array, which is much faster than making an array with push.

I will note, except for the even bit (with should cut your time in half), these changes will be pretty small unless num is big.

10

I didn’t even think about bit shifting. Pretty smart solution. I will implement it. Again thank you so much for your guidance.

1 Like