The Sieve of Eratosthenes

An ancient but infallible method for identifying prime numbers

One of the most effective methods for identifying prime numbers within the far larger series of composite numbers was invented over twenty-two centuries ago. It is the so-called sieve of Eratosthenes. Its inventor was the mathematician and astronomer Eratosthenes of Cyrene, in today’s Libya, a man of multifaceted genius, famous above all for having been the first to calculate the Earth’s circumference, obtaining with the modest technologies of his time a measure surprisingly close to what today we know to be the correct one.

The sieve of Eratosthenes works in a very simple way. The first step consists in creating a table containing in ascending order all the positive integers whose primality is to be tested, starting from 2. (Since 1 is not a prime number, it does not need to be included in the table.)

We start by skipping 2 and canceling from the table all its multiples: 4, 6, 8, 10, etc. This step, the longest and most tedious of the whole process, can be avoided by creating a table where 2 is followed only by odd numbers. The final result will not change, as 2 is the only even prime.

Then, we move on to the next non-canceled number in the table, which is 3. Let us skip 3 and cancel out all its multiples. The work to…