The Sieve of Eratosthenes: An Ancient Greek Method of Finding Primes

Throughout mathematical history, thinkers have attempted to come up with a great many methods by which to discover prime numbers. Eratosthenes' was perhaps the simplest.

Eratosthenes (c. 276 - 195 B.C.) was an important Greek thinker - a philosopher, astronomer, mathematician and poet - who produced some very important work which followed up on many of his most notable Greek predecessors, such as Aristotle and Euclid.

image credit

Perhaps Eratosthenes' most famous contribution to early thought was his shockingly accurate measurement of the circumference of the Earth (yes, they knew that the Earth was round even 1700 years before Columbus); a measurement he performed by calculating the angle of the sun's shadow at the same time of day at two different locations on the Earth and analyzing the minute difference between them. His methods may seem somewhat primitive but his results were nothing short of astonishing (though just how accurate he was is not precisely known, for the units of measurement he used are outdated and their exact length is uncertain).

Somewhat more overlooked than Eratosthenes' measurement of the Earth, however, was his rather fascinating and wholly simple creation which aided in analyzing one of the most fascinating subjects in all of number theory - Prime Numbers.

image credit

Creating the Sieve

A prime number, of course, is merely a number which cannot be divided by any number other than itself and 1. Three, five, seven, eleven, and thirteen are all examples of prime numbers, and while it is rather simple to determine the primacy of these relatively low integers, the questions become profoundly more difficult as the numbers get higher.

Certain questions regarding primes have always been difficult, due to the fact that even today a method has not yet been discovered to determine whether or not a given number is genuinely prime without going through the motions of actually trying to divide it by every smaller number. So even a simple question can actually prove to be remarkably time consuming when discussing prime numbers. A prime (no pun intended) example of this is a question such as: How many prime numbers are their below 100?

While Eratosthenes would not discover a method of instantly discovering an answer to a question such as this, he was able to develop a rather interesting little trick which aids in the process, and which is simple enough that even those who are not intimately familiar with number theory can understand it.

To begin with, Eratosthenes began with a simple table of numbers, such as a 10 x 10 table which covered every number between one and one hundred.

From here, discovering every prime number below one hundred is just a simple process of elimination. Every number which is not a prime number was crossed off, one by one.

Using the Sieve

To use his sieve, Eratosthenes first crossed off the number one, which is certainly not a prime number. Then, beginning with the number 2, Eratosthenes crossed off every multiple of that number; 4, 6, 8, 10, all the way up to 96, 98 and 100. Because all of those numbers are divisible by 2, they cannot be prime numbers.

Next, Eratosthenes moved up to the next lowest number which was not yet crossed off, which is 3. Then, he went through and crossed off every multiple of 3 to be found in the table; 6, 9, 12 . . . 96, 99. Only 34 numbers are left which are not crossed off.

Now he skips the number four (which is already crossed off) and moves up to the next prime, 5, and crosses off all of its multiples. 28 possible primes left.

Now multiples of 7, leaving 25 primes. And that is it. With just seven steps all of the non-primes are crossed off of the list and only the primes remain. All the numbers between 1 and 100 have passed through the sieve and only the primes have come out the other side.

Further Implications of the Sieve

In addition to providing a convenient method for finding the number of primes within a certain range by way of a very simple table and a process of elimination, the Sieve of Eratosthenes can also be changed and adapted - resized and reshaped - in order to discover some very fascinating patterns which begin to crop up in the distribution of prime numbers.

In addition, it becomes clear when using the sieve for larger numbers that as the numbers grow higher and higher, prime numbers grow few and far between, though they certainly continue to exist (it has been proved at many times and in many different ways that there does not exist a "highest" prime number - there will always be more). The sieve allows a fascinating look into the extreme difficulties to be found in attempting to mathematically quantify the distribution of prime numbers - a subject which has fascinating the minds of even the greatest mathematicians for more than two and a half millennia.

A Great Sieve of Eratosthenes Resource

"Eratosthenes." The University of Utah http://www.math.utah.edu/~alfeld/Eratosthenes.html