In a real Sieve implementation, your "sieve" is the array that keeps track of the multiples of primes. You'll also want to remember the values of the primes, since the array is basically an array of Boolean values.
Thus, the first thing you do is create the array. It has to be as big as the biggest target value:
function primesBelow(n) {
var sieve = new Array(n);
Upon initialization, that array is empty, and thankfully in JavaScript empty array elements look false. So we start with 2:
var primes = [];
for (var test = 2; test < n; ++test) {
if (sieve[test]) {
// NOT PRIME
}
else {
If the sieve value is unset at a particular test number, that means that that value is the multiple of no known prime. Hence, we can tick ofoff that sieve entry (even though we'll never see it again) and all multiples of that newly-found prime:
primes.push(test);
for (var pm = test; pm < n; pm += test)
sieve[pm] = true;
}
}
(Note that we really could start the value of pm at test * test, because the first composite number bigger than test for which test will be the only prime factor will be its square.)
When we start the loop at 2, the first prime we find is, clearly, 2 itself, since the sieve is freshly created and completely empty. So all the multiples of 2 will be set to true on the first pass. The second value to test is 3, and sieve[3] will still be false, because 3 is not a multiple of 2 and is therefore also prime.
The first composite number encountered will be 4, because its slot in the sieve will have been set to true when we found 2. Then 5 will be tested, and its sieve slot will also be empty, so it's prime too.
Note that the first odd composite number to be found is 9, which is not prime because its sieve slot will have been set to true when the loop found 3.
The complete code:
function primesBelow(n) {
var sieve = new Array(n);
var primes = [];
for (var test = 2; test < n; ++test) {
if (sieve[test]) {
// NOT PRIME
}
else {
primes.push(test);
for (var pm = test; pm < n; pm += test)
sieve[pm] = true;
}
}
return primes;
}
