algorithm - Can you explain this method of finding prime numbers in javascript - Stack Overflow

admin管理员组

文章数量:1404924

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.

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.

• javascript
• algorithm
• primes

Share Improve this question Follow edited Jun 23, 2013 at 21:21 Drew Noakes 312k171171 gold badges698698 silver badges765765 bronze badges asked Jun 23, 2013 at 20:54 Muhammad UmerMuhammad Umer 2,30833 gold badges1919 silver badges1717 bronze badges 6

• 1 The << operator is a bitwise left shift. Shifting by 1 is going to multiply by 2, so j = i * 2 would do the same thing. – nnnnnn Commented Jun 23, 2013 at 20:55
• 1 en.wikipedia/wiki/Sieve_of_Eratosthenes – Achrome Commented Jun 23, 2013 at 20:56
• 2 Ugh, the "right shift instead of multiplying by two" thing. Premature optimization at its worst. (And utterly pointless since any piler/interpreter worth its salt will do that automatically anyway.) – Imre Kerr Commented Jun 23, 2013 at 21:05
• i didn't write this so yea lol – Muhammad Umer Commented Jun 23, 2013 at 21:36
• There is another potential bug lurking here when discussing the difference between multiplying by two and using a bitwise left shift. The bitwise left shift operator produces a signed 32 bit result (ecma-international/ecma-262/5.1/#sec-11.7.1). Where as multiplication by default produces double-precision (ecma-international/ecma-262/5.1/#sec-11.5.1) – veritasetratio Commented Jun 23, 2013 at 23:00

 |  Show 1 more ment

2 Answers 2

Sorted by: Reset to default 5

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.

It uses the Sieve of Eratosthenes.

From Wikipedia ( http://en.wikipedia/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.

本文标签： algorithmCan you explain this method of finding prime numbers in javascriptStack Overflow