What does this line mean in a getPrimes algorithm?

Question

var fs = require('fs');
var outfile = "primes.txt";
function getPrimes(max) {
    var primeSieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!primeSieve[i]) {
            // i has not been marked - it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                primeSieve[j] = true;
            }
        }
    }
    return primes;
}
fs.writeFileSync(outfile,  getPrimes(1000).slice(0,100) + ",");
console.log("Script: " + __filename + "\nWrote: " + getPrimes(1000).slice(0,100) + "To: " + outfile);

I have the above piece of code that I modified to produce an output (the main algorithm provided by someone else). I am new to Javascript and am unsure of what the following line is actually doing and what the << operator means (I have been unable to find out on the Javascript website).

for (j = i << 1; j <= max; j += i)

I know that it is marking the relevant numbers in the main primeSieve array as true so that they do not populate the primes array, however I don't know how it is doing this.

MDN explains the [bitwise shift left](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators#<<_(Left_shift)) operator. I understand that it's hard to google an operator when you don't know what it's called, but MDN has a [list of all JS operators](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators). (Not that MDN is the only site with JS information, but it is a good site.) — nnnnnn, Jun 23 '13 at 02:25
Like @nnnnnn said the << is a bitshift so `1 << 1 = 2` and `8 << 1 = 16` — JasonM, Jun 23 '13 at 02:25

score 1 · Answer 1 · edited May 23 '17 at 11:56

1

The << operator is the left shift operator. The left argument (after conversion to an integer value, if necessary) is shifted to the left by the number of bits specified by the right argument, right-filling with zeroes. Shifting left by one is the same as multiplying by 2.

The inner loop simply stores true in every element of primeSieve that is at an index that is a multiple of i. Thus, if primeSieve[j] is true, then j must be a multiple of some previous i (hence j cannot be prime). Conversely, if primeSieve[i] is not true, then it was not a multiple of any previous value of i; since that includes all integers from 2 to i-1, i must then be prime.

For collecting all primes up to a certain maximum, this method is far superior to techniques that independently test each integer for primality. However, it is far from the most efficient method. For instance, note that an element of primeSieve might get set to true several times. For instance, primeSieve[6] is set when i==2 and again when i==3. Also, once i exceeds the square root of max, the inner loop is a waste, since all composite numbers up to max are guaranteed to have been marked at that point. See the Wikipedia article on the Sieve of Eratosthenes for more about how this all works and pointers to even more efficient methods.

P.S. That code looks suspiciously familiar. :-)

edited May 23 '17 at 11:56

Community

1
1

answered Jun 23 '13 at 02:24

Ted Hopp

232,168
48
399
521

ha yes it is your code, I was going to ask the question in that thread but as it was quite old I asked a new question. I'm still unsure of where the test for primality is on the chosen number? – Anthony Fawkes Jun 23 '13 at 02:32
Any number that satisfies the conditions that it is equal to 2*i and less than the max number and equal to itself plus i is not a prime and all other numbers are? – Anthony Fawkes Jun 23 '13 at 02:37
@AnthonyFawkes - Think of the sieve as a list of known composite numbers. Starting at 2 (the smallest prime), the outer loop goes through all numbers (up to `max`) checking whether the number is a known composite. If not, the number is pushed onto the list of primes and the inner loop marks all multiples of that number as composite. This works to detect primes because the numbers are examined in increasing order and none are skipped. I recommend reading about the [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes); the article includes more efficient sieve tricks. – Ted Hopp Jun 23 '13 at 02:45
Ah I think I understand now, so the inner loop is only executed on a number that has been pushed to the primes array. It runs through the multiples (done with the j += i) starting with the first multiple which would be 2*i up to max marking them as true and then the outer loop is executed again for the next number until it finds another number it can push to the primes array. Thanks!! – Anthony Fawkes Jun 23 '13 at 02:58

What does this line mean in a getPrimes algorithm?

1 Answers1