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 start^{2} since all of the numbers below that will eventually be marked off. Second, we can stop out algorithm once start^{2} 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 }, []) }