# Sieve of Eratosthenes

## Sieve of Eratosthenes

Algorithm that makes it possible to find all the prime numbers up to a given number.

This algorithm is described by these instructions:

To find all of the prime numbers up to a given number n:

1. Write a list of all the whole numbers from 1 to n in a table;
2. Eliminate 1, which is not a prime number;
3. Mark 2 and eliminate all multiples of 2;
4. Do the same with 3;
5. Choose the next least number not underlined and not eliminated (here, 5);
6. Eliminate all of its multiples;
7. Repeat the process up to the whole part of the square root of n.

The marked numbers are the prime numbers up to n.

### Example

If we want to find all of the prime numbers up to 50, we must first determine the whole part of the square root of 50, which is 7, because the square root of 50 is about 7.07.

First, eliminate the number 1.
Eliminate all multiples of 2 except 2.
Eliminate all multiples of 3 except 3.
Eliminate all multiples of 5 except 5.
Eliminate all multiples of 7 except 7.

The circled numbers are what is left and they represent the prime numbers up to 50.

### Historical note

When Archimedes was studying math in Syracuse, another talented mathematician joined the staff at the Museum of Alexandria in Egypt at the request of the Pharaoh Ptolemy III: Eratosthenes of Cyrene (modern-day Libya). He was a poet, historian, geographer, astronomer, athlete and mathematician, as well as the tutor to the Pharaoh’s son and the chief librarian at the University of Alexandria.