Sieve of Eratosthenes
The Sieve of Eratosthenes is one of the oldest-known algorithms, and it’s still helpful for deriving prime numbers! The algorithm is attributed to Eratosthenes, a Greek mathemetician born in the third century BCE.
1 and itself.
443 are all prime numbers.
The sieve works by first assuming that all numbers from
are prime, and then successively marking them as NOT prime.
The algorithm works as follows:
- Create a list of all integers from 2 to n.
- Start with the smallest number in the list (2, the smallest prime number).
- Mark all multiples of that number up to n as not prime.
- Move to the next non-marked number and repeat this process until the entire list has been covered.
When the steps are complete, all remaining non-marked numbers are prime.
If we wanted to find all prime numbers less than or equal to 10, we would:
Start with a list where all are assumed to be prime:
2, mark all multiple up to
10as NOT prime:
Move to the next non-marked number,
3, and mark its multiples as NOT prime (
6) is already marked:
Continue marking, starting with every non-marked number (in this case, all multiples of
5are already marked, and
7‘s first multiple is out of range). This means that we have now found all primes up to
This animation shows the whole process for primes from 1 to 100:
- Create an array of all integers from
- Set all elements of the array to
- Starting with
2, iterate through the array. If the current element is
true, it is still considered prime. Since we know that all multiples of that number are NOT prime, iterate through all multiples of that number up to
nand set them equal to
- Change the current element to the next non-
- Return the corresponding number value for any element still marked as prime (value of
If you’d like to try your hand at implementing the algorithm using these steps, jump to the complete algorithm code block below. Otherwise, we’ll do walk through a step-by-step breakdown below.
First, we’ll create the array. In this case, we’ll create an array to represent all numbers up to the input limit, but we’ll use the array index to represent the number, and its value (
false) to represent whether it is prime or not. The original algorithm said to use an array of
2, ..., n, but since we’re using indices to represent the actual number, we’ll start the array from
0 and essentially ignore the values of
For example, after running our sieve, an array representing the primes up to
7 would look like this, with elements at
[false, false, true, true, false, true, false, true]