History of Mathematics Project | The Sieve of Eratosthenes

History of
Mathematics

Project

around 200 BCE

The Sieve of Eratosthenes

Finding the primes by crossing out everything that isn’t

The sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit by crossing out multiples of numbers.

The earliest known reference to the sieve of Eratosthenes for finding prime numbers is in Introduction to Arithmetic by Nicomachus of Gerasa (60–120 CE), which describes it and attributes it to Eratosthenes of Cyrene (around 276–194 BCE), a Greek mathematician. Nicomachus was translated into Arabic by Thābit ibn Qurra (d. 901).

Artifact format

Unknown (lost)

Original artifact location

Kyrene (historical name), Sahhat, Libya (current name)

Timeline

Interactive Content

Computational Explanation

The sieve of Eratosthenes constructs a list of all prime numbers up to some maximum limit by crossing ("sieving") out multiples of incrementally larger numbers, leaving only primes at the conclusion of the algorithm.

To find all prime numbers up to 100, start with all positive integers between 1 and 100:

In[]:=

result=Range[100]

Out[]=

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100}

Since the number 1 is a special case that, at least by modern convention, is not considered a prime number (this is because it has only a single factor: itself), it can be immediately excluded:

In[]:=

result=Rest[result]

Out[]=

{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100}

The first step in the sieve removes all nontrivial multiples of 2 (i.e. multiples other than the number 2 itself):

In[]:=

result=Complement[result,Range[22,100,2]]

Out[]=

{2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99}

The second step removes all nontrivial multiples of 3:

In[]:=

result=Complement[result,Range[23,100,3]]

Out[]=

{2,3,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,73,77,79,83,85,89,91,95,97}

Since 4 has already been removed, the next step removes multiples of 5:

In[]:=

result=Complement[result,Range[25,100,5]]

Out[]=

{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97}

And finally multiples of 7:

In[]:=

result=Complement[result,Range[27,100,7]]

Out[]=

{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}

To cover numbers up to n, only factors up to

need to be sieved out. Since

100

10

and since no other numbers less than or equal to 10 remain in the above list, it therefore gives the complete list of primes up to 100.

This can be easily verified using the built-in Wolfram Language function PrimeQ:

In[]:=

Select[Range[100],PrimeQ]

Out[]=

{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}

It can also be verified using Prime and PrimePi:

In[]:=

Prime[Range[PrimePi[100]]]

Out[]=

{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}

Other Resources

Wolfram Demonstration
Sieve of Eratosthenes

Wolfram Demonstration
Prime Factorization Tables

Additional Reading

D'Ooge, M. L. (trans.). Nicomachus of Gerasa: Introduction to Arithmetic. With Studies in Greek Arithmetic by Frank Egleston Robbins and Louis Charles Karpinski. New York: Macmillan, 1926.
Hoche, R. (trans.). Nicomachi Geraseni Pythagorei Introdvctionis arithmeticae libri II. Leipzig, Germany: Teubner, 1866.
Horsley, Rev. S. "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an Account of his Method of Finding all the Prime Numbers." Philosophical Transactions of the Royal Society of London (1683–1775), Vol. 62, pp. 327–347, 1772.
Kutsch, W. (Ed.). Ṯābit B. Qurra's arabische Übersetzung der 'Arithmētikē eisagōgē' des Nikomachos von Gerasa. Beyrouth: Imprimerie Catholique, 1959.
Pappas, T. The Joy of Mathematics: Discovering Mathematics All Around You. San Carlos, CA: Wide World Publishing/Tetra, pp. 100–101, 1989.