Sum All Primes - adding to the sieve

Sum All Primes - adding to the sieve
0
#1

Hi everyone. Can someone explain why “sieve.push(j)” below doesn’t work to add the multiples of i to sieve (the list of composite numbers?) I’ve seen from a few solutions that sieve[j]=true works instead, but I never would have thought of that, so I’d like to understand why my more beginner approach doesn’t do the trick. Thanks in advance for any suggestions!

function sumPrimes(num) {
  //sieve for composites, primes for primes
  var i, j, k, total=0, sieve=[], primes=[];
  //if i hasn't been added to sieve, add to primes and add all of its multiples to sieve up to num/max
  function getPrimes(max) {
    for (i=2; i<=max; i++) {
      if (sieve.indexOf(sieve[i]) < 0) {
        primes.push(i);       
        for (j = i*2; j<=max; j+=i) {
          sieve.push(j);         
        }
      }
    }
    return primes;
  }
  
  //Add up primes.  Need to call getPrimes using num
    primes = getPrimes(num);
  for (k = 0; k<primes.length; k++ ) {
    total+= primes[k];
  }
  return total;
#2

Something I notice immediately: you’re using

sieve.indexOf(sieve[i])
over
sieve.indexOf(i)

Since you are checking whether a number i is in the sieve, not if the number at position i of the sieve is in the sieve (which will be an unpredictable value).

An example:

looping i from 2 to 10: 

i=2
inserted 2 in primes as sieve is empty
inserted 4, 6, 8, 10 in the sieve.

i=3
checked if sieve[3] is in in sieve
sieve[3] = 10 (!!!)
Don't insert 3 in primes and continue..

So you should be checking indexOf(3) not indexOf(sieve[3]).

Also, isn’t a boolean array for the sieve more intuitive? Every value just tells you whether an element is prime or not.

EDIT: Tested and this was indeed the issue.

#3

Wow - thank you. What a bone-headed mistake! Oddly enough, however, after correcting it now my code doesn’t pass, even when I use sieve[j]=true instead of sieve.push(j). (And for some reason my code passes if I use sieve[j]=true and don’t correct the mistake you noted??) I’m going to have to give this a little more thought.

You are right that using the boolean approach makes cleaner logical sense, but at my stage I suppose I lean too heavily on trying to cobble together whatever methods I’ve used previously and become comfortable with rather than trying to more cleanly solve the problem. Definitely hoping that changes over time . . .

Thanks again.

#4

I just changed the line I mentioned and it passed for me, which is why I made the edit.

As for using sieve[j]= true, you ended up using the algorithm the way it’s usually used.

When you used push your array would’ve looked like:

0:4
1:6
2:8

When you use sieve[j] = true, your array looks like this:

0:undefined
1:undefined
2:undefined
3:undefined
4:true
5:undefined
6:true

Since every non prime number will get assigned a value (true), they will return some value when you check them. (Note that every non prime number is in the sieve before you even check this condition so this is always true). You could try assigning any value (say 223 or 3434) and the result would be the same.

This is because you would never have a value in the sieve for a prime number, and thus sieve[somePrimeNumber] will always be undefined, thus it’s index will be -1. This is a trick that would only work with JS or languages like JS though, because other languages usually won’t let you assign values to arrays like a dictionary. Nonetheless, the logic is sound and and is close to how most people use the sieve of Eratosthenes.

As for using a boolean array, it’s useful because you can check if a number is prime in constant time. After building a sieve you can just check if sieve[number] is true or not and use it for the problem. Whereas checking the index of a number in a array is an operation that takes longer as your sieve size grows, even with binary search. So if you have to get primes till 100,000 and then print only the even primes, a boolean array would be significantly faster.

Hope this helps!