Sieve of Eratosthenes

Sieve of Eratosthenes is an almost mechanical procedure for separating out composite numbers and leaving the primes. It was invented by the Greek scientist and mathematician Eratosthenes who lived approximately 2,300 years ago.

The natural numbers 1, 2, 3, 4,... can be classified into three groups: the prime numbers, which have no proper divisors other than 1; the composite numbers, which have two or more proper divisors; and 1 itself, which is neither prime nor composite. Thus 2, 3, and 5 are primes, while 4, 6, and 8 are composite. (A proper divisor of a given number is a whole number which is smaller than the given number and divides it without a remainder.) If one writes the natural numbers in order, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,..., every second number will be a multiple of 2; every third number, a multiple of 3; every fourth number, a multiple of 4; and so on. Eratosthenes' sieve makes use of this fact.

First, one writes the natural numbers in order, omitting the 1. Then one circles the 3 and crosses out every third number, including 6 and 12, which are already crossed out. The numbers that are left have neither 2 nor 3 as divisors.

One continues this process for as long as one likes. The circled numbers, 2, 3, 5, 7, 11, 13,...are primes; the crossedout numbers, 4, 6, 8, 9, 10, 12, 14,... are composite.

Although the sieve can be a tedious process for discovering large primes, it is still very useful. For one thing, it involves no arithmetic other than counting. For another, if one uses it for the first n natural numbers, it will pick out all the primes in that range. Furthermore, it is a procedure that can be effectively turned over to a computer, using a language such as Fortran, BASIC, or Pascal. According to Ore, every table of primes has been constructed with the method described by Eratosthenes. This includes tables of all the primes up to one hundred million.

What it will not do is provide a simple test of a given number. In order to decide by means of the sieve whether a number such as 9577 is prime, one would have to find all the primes up to 9577. One cannot use the sieve to test the number directly.

Actually doing this, although tedious, is not quite as bad as it sounds. If 9577 is going to be crossed out, it will have been crossed out by the time one circles 97 and crosses out every ninety-seventh number beyond. The reason for this is that for 9577 to be composite, it must be the product of two factors, say p and q. That is, 9577 = pq. The larger of these factors must be equal to or greater than the square root of 9577; and the smaller, less than or equal to it. Since the square root of 9577 is approximately 97.86, one of its supposed factors has to be 97 or less. Of course, that is still a lot of work. There are twenty-four primes less than 97, with circling and crossing out to be done for each one of them.

As this example shows, the crossing out process is more efficient than it first appears to be. In general, if one crosses out all the multiples of primes up to, and including a number n, then all the composite numbers up to and including the square of n will have been crossed out. When one crosses out all the multiples of 2 and 3, all the composite numbers up to 9 have been crossed out, and this can be verified by the example above. Crossing out the multiples of 2, 3, and 5 crosses out all the composite numbers up to and including 25. The examples above don't extend far enough to show this, but the reader can check it for himself or herself.

There is a variation on the sieve that allows one to do more than sort the natural numbers into two classes. In this procedure one writes the natural numbers in the following array. In the second row one starts under the 2 and skips one space between each of the natural numbers. In the third row one starts under the 3 and skips two spaces, and so on.

This procedure lists all of a number's proper divisors directly below it. Thus 7 has only 1 as a proper divisors directly below it, while 12 has 6, 4, 3, 2, and 1. Seven is therefore a prime number, and 12 is composite.