Skip to main content

Sieve of Eratosthenes

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 crossed-out 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

KEY TERMS

Proper divisor A natural number which divides a given natural number without a remainder, and is smaller than the given number.

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 dont 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 numbers 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.

J. Paul Moulton

Cite this article
Pick a style below, and copy the text for your bibliography.

  • MLA
  • Chicago
  • APA

"Sieve of Eratosthenes." The Gale Encyclopedia of Science. . Encyclopedia.com. 19 Nov. 2018 <https://www.encyclopedia.com>.

"Sieve of Eratosthenes." The Gale Encyclopedia of Science. . Encyclopedia.com. (November 19, 2018). https://www.encyclopedia.com/science/encyclopedias-almanacs-transcripts-and-maps/sieve-eratosthenes-0

"Sieve of Eratosthenes." The Gale Encyclopedia of Science. . Retrieved November 19, 2018 from Encyclopedia.com: https://www.encyclopedia.com/science/encyclopedias-almanacs-transcripts-and-maps/sieve-eratosthenes-0

Learn more about citation styles

Citation styles

Encyclopedia.com gives you the ability to cite reference entries and articles according to common styles from the Modern Language Association (MLA), The Chicago Manual of Style, and the American Psychological Association (APA).

Within the “Cite this article” tool, pick a style to see how all available information looks when formatted according to that style. Then, copy and paste the text into your bibliography or works cited list.

Because each style has its own formatting nuances that evolve over time and not all information is available for every reference entry or article, Encyclopedia.com cannot guarantee each citation it generates. Therefore, it’s best to use Encyclopedia.com citations as a starting point before checking the style against your school or publication’s requirements and the most-recent information available at these sites:

Modern Language Association

http://www.mla.org/style

The Chicago Manual of Style

http://www.chicagomanualofstyle.org/tools_citationguide.html

American Psychological Association

http://apastyle.apa.org/

Notes:
  • Most online reference entries and articles do not have page numbers. Therefore, that information is unavailable for most Encyclopedia.com content. However, the date of retrieval is often important. Refer to each style’s convention regarding the best way to format page numbers and retrieval dates.
  • In addition to the MLA, Chicago, and APA styles, your school, university, publication, or institution may have its own requirements for citations. Therefore, be sure to refer to those guidelines when editing your bibliography or works cited list.