Can you explain this method of finding prime numbers in javascript

Question

function getPrimes(max) {
var sieve = [], i, j, primes = [];
for (i = 2; i <= max; ++i) {
    if (!sieve[i]) {
        // i has not been marked -- it is prime
        primes.push(i);
        for (j = i << 1; j <= max; j += i) {
            sieve[j] = true;
        }
    }
}
return primes;
}

I understant that i keeps track of all numbers.

i don't understand...!sieve[i],j = i << 1; & what is really happening.

Just to be Clear.. Prime Number is something that is only divisible by itself or by one.

Answer 1

It's called the Sieve of Erathestenes and it's an efficient way of finding all prime numbers between zero and some upper limit integer.

j = i << 1

This is a bit shift operation. It shifts an integer 1 bit to the left. Because binary is base two, this is equivalent to multiplying by two. In decimal, the equivalent operation would be shifting, say, 1 to the left and bringing in a zero to the right. It's base ten, so you end up with 10 (ten times one.)

I don't believe the implementation you show is optimal. The limit to the i value can be lower -- something like sqrt(max).

You can easily find some really nice animations online of this algorithm that show you what's going on in quite an intuitive way.

Answer 2

It uses the Sieve of Eratosthenes.

From Wikipedia ( http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes )

A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

• Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
• Initially, let p equal 2, the first prime number.
• Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These will be multiples of p: 2p, 3p, 4p, etc.; note that some of them may have already been marked.
• Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime. The main idea here is that every value for p is prime, because we have already marked all the multiples of the numbers less than p.