Craig Rodrigues!

Jun 7 The Sieve of Eratosthenes in JavaScript

The Sieve of Eratosthenes is a simple algorithm for finding all of the prime numbers up to a certain limit (or between two numbers).

If you wanted to find all the Prime numbers between 2 and 100 you could iterate from 2 to 100 and test if that number itself were a prime, but ain't no one got time for that.

Since a Prime number is only divisible by itself and 1, we can start from 2, and continually flag every multiple of that number up to n as false (not a prime). The next number would be 3, then we can mark every multiple of 3 to n as false.

Here is a great visualization from Wikipedia So for example, if we wanted to find all the primes between 2 and 20 we would start listing all the numbers out.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

We can start with 2 and loop through our list marking off every multiple of 2 until we reach 20.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Then we go to 3 and mark off every multiple of 3 that hasn't already been flagged.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

We continue this until we reach the end. We are left with only the prime numbers between 2 and 20 which are:

2 3 5 7 11 13 17 19

There are some improvements we can add to make our algorithm a bit faster though!

First, we can start marking off numbers from start2 since all of the numbers below that will eventually be marked off. Second, we can stop out algorithm once start2 is greater than n since we know that any multiple of that number as been marked off and will be beyond n.

Here is our finished implementation in JavaScript:

const sieve = max => {
// Make array of length max and fill with true
const sieve = new Array(max).fill(true)

// Iterate from 2 until square root of max
for (let i = 2; i < Math.sqrt(max); i++) {
// If the number is labelled a prime then we can start at i^2 and mark every multiple of i
// from there as NOT a prime
if (sieve[i]) {
for (let j = Math.pow(i, 2); j < max; j += i) {
sieve[j] = false
}
}
}

// Now we can reduce our sieve to only the Prime indexes that are true
return sieve.reduce((primes, isPrime, i) => {
if (isPrime && i > 1) {
primes.push(i)
}

return primes
}, [])
}