Filtering Prime Numbers using the Sieve of Eratosthenes

What is the Sieve of Eratosthenes?

Last week’s article, A Brief Introduction to Prime Numbers, mentioned the “Sieve of Eratosthenes” – a procedure devised by the clever Greek philosopher Eratosthenes. As a sieve catches fish, but allows water to escape, the Sieve of Eratosthenes retains prime numbers but allows composite numbers to pass through.

Essentially, the Sieve is a simple way of listing all prime numbers up to some predetermined number. The image shows an Eratosthenes’ Sieve with an upper limit of 26.

"Sieve of Eratosthenes to 26" by Mike DeHaan

“List#1″, the leftmost column, shows all the potential prime numbers from 2 to 26.

“List#2″ changes the multiples of ’2′ to red text and puts a light pink background behind them.

“List#3″ starts with the next prime, ’3′. Every odd multiple of ’3′ changes to red and receives a darker hue of pink background. As an intelligent human, I did not need to re-eliminate the even multiples of 3, such as ’6′. I saw it had already been eliminated.

“List#4″ eliminates those multiples of ’5′ that survived the previous primes.

Notice that “List#5″ looks exactly like “List#4″. I was going to eliminate the multiples of ’7′, but ’14′ and ’21′ had already been removed by ’2′ and ’3′ respectively.

Four Special Features of the Sieve of Eratosthenes

First, one only needs to begin eliminating numbers at the square of the prime, which is not usually the first multiple of that prime. “List#2″ had its first elimination at 2^2=4. “List#3″ began eliminating new composite numbers at 3^2=9. “List#4″ saw its first change at 5^2=25.

Secondly, this is a nice problem in computer programming. If the assignment calls for a finite upper limit, it is easy to start by populating a fixed array.

The third feature is that this programming problem could be stated as “Build the Sieve without starting with an upper number boundary; just stop after a certain number of seconds but report the primes as they are found”. The process as described above does not lend itself to an infinitely long table: one would never finish eliminating the even numbers!

Finally, a person might feel more efficient than a computer program. By looking at the colours in the spreadsheet, I felt no need to re-examine ’12′ when eliminating multiples of ’3′. The computer algorithm would likely have “eliminated” the number ’12′ twice.

How Useful is the Sieve of Eratosthenes?

Portrait of ancient Greek philosopher and mathematician Eratosthenes

The Sieve of Eratosthenes is valuable in at least two situations. First, after one first builds a lengthy list of primes, it is easy to recognize whether some random number in that range is prime.

Secondly, one might need “the next prime number” or “a higher prime number” or simply “just another prime number”. The Sieve of Eratosthenes is a convenient list from which to choose primes.

Gödel’s “Incompleteness Theorem”, for example, uses the products of prime numbers to represent expressions in a formal language of a system of arithmetic.

Other mathematicians and programmers have worked on more efficient sieves, and other methods of calculating prime numbers, but those not competing to build the largest set of prime numbers are likely to be content with the Sieve of Eratosthenes.

Caldwell, C. K. University of Tennessee at Martin. Sieve of
Eratosthenes
. (1999-2011). Accessed Oct. 22, 2011.

© Copyright 2011 Mike DeHaan, All rights Reserved. Written For: Decoded Science