Sieve of Eratosthenes

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.^[1] This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.^[2] Once all the multiples of each discovered prime have been marked as composites, the remaining unmarked numbers are primes.

The earliest known reference to the sieve (Ancient Greek: κόσκινον Ἐρατοσθένους, kóskinon Eratosthénous) is in Nicomachus of Gerasa's Introduction to Arithmetic,^[3] an early 2nd cent. CE book which attributes it to Eratosthenes of Cyrene, a 3rd cent. BCE Greek mathematician, though describing the sieving by odd numbers instead of by primes.^[4]

One of a number of prime number sieves, it is one of the most efficient ways to find all of the smaller primes. It may be used to find primes in arithmetic progressions.^[5]

^ Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," Philosophical Transactions (1683–1775), Vol. 62. (1772), pp. 327–347.
^ Cite error: The named reference ONeill was invoked but never defined (see the help page).
^ Hoche, Richard, ed. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, chapter XIII, 3, Leipzig: B.G. Teubner, p. 30
^ Nicomachus of Gerasa (1926), Introduction to Arithmetic; translated into English by Martin Luther D'Ooge; with studies in Greek arithmetic by Frank Egleston Robbins and Louis Charles Karpinski, chapter XIII, 3, New York: The Macmillan Company, p. 204
^ J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", Annals of Mathematics, Second Series 10:2 (1909), pp. 88–104.

[horsley-1] Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," Philosophical Transactions (1683–1775), Vol. 62. (1772), pp. 327–347.

[ONeill-2] Cite error: The named reference ONeill was invoked but never defined (see the help page).

[nicomachus-3] Hoche, Richard, ed. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, chapter XIII, 3, Leipzig: B.G. Teubner, p. 30

[nicomachus1926-4] Nicomachus of Gerasa (1926), Introduction to Arithmetic; translated into English by Martin Luther D'Ooge; with studies in Greek arithmetic by Frank Egleston Robbins and Louis Charles Karpinski, chapter XIII, 3, New York: The Macmillan Company, p. 204

[5] J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", Annals of Mathematics, Second Series 10:2 (1909), pp. 88–104.

[1]

[2]

[3]

[4]

[5]