Sieve of Eratosthenes

From Wikipedia, the free encyclopedia

Jump to: navigation, search
Sieve of Eratosthenes: algorithm steps for primes below 120 (including optimisation of starting at squares)

In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer[1]. It works efficiently for the smaller primes (below 10 million) [2]. It was created by Eratosthenes, an ancient Greek mathematician. When the Sieve of Eratosthenes is used in computer programming, wheel factorization is often applied before the sieve to increase the speed.


[edit] The algorithm

  1. Create a contiguous list of numbers from two to some highest number n.
  2. Strike out from the list all multiples of two (4, 6, 8 etc.).
  3. The list's next number that has not been struck out is a prime number.
  4. Strike out from the list all multiples of the number you identified in the previous step.
  5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
  6. All the remaining numbers in the list are prime.

[edit] Algorithm details and complexity

The crossing-off of multiples of each found prime number can be started at the square of the number, as lower multiples have already been crossed out during the previous steps.

The complexity of the algorithm is O((nlogn)(loglogn)) with a memory requirement of O(n)[3]. The segmented version of the sieve of Eratosthenes, with basic optimizations such as wheel factorization, uses O(n) operations and O(n1 / 2loglogn / logn) bits of memory[4].

David Turner [5] suggested in 1975 that the sieve of Eratosthenes could be represented in a strikingly simple and elegant way in purely functional programming languages. Turner's sieve, rendered in Haskell, is:

primes = sieve [2..]
sieve (p : xs) = p : sieve [x | x <− xs, x `mod` p > 0]

However, Melissa O'Neill [6] showed that the complexity of Turner's algorithm is significantly worse than the complexity of the classical imperative renditions of the sieve. O'Neill demonstrated simple renditions of the sieve of Eratosthenes in Haskell with complexities similar to those of the classical algorithms.

A more lucid version of the algorithm for demonstrative purposes is the following function, written in Python:

def primeSieve(upperBound):
    Returns a list of all prime numbers less than upperBound.
    numbers = range(2, upperBound)
    primes = []
    while numbers:
        prime = numbers.pop(0)
        numbers = [n for n in numbers if n % prime]
    return primes

[edit] Mnemonic

A poem, replicating the essence of the algorithm, is as follows:[7][8]

Sift the Twos and sift the Threes,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

[edit] See also

[edit] References

  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.
  2. ^ The Prime Glossary: "The Sieve of Eratosthenes",, references 16. November 2008.
  3. ^ Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci. Comput. Programming 9:1 (1987), pp. 17–35.
  4. ^ A. O. L. Atkin and D. J. Bernstein, "Prime sieves using binary quadratic forms", Mathematics of Computation 73 (2004), pp. 1023–1030.
  5. ^ Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975.
  6. ^ O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 09 Oct 2008 doi:10.1017/S0956796808007004.
  7. ^ Merritt, Doug (December 14, 2008). "Sieve Of Eratosthenes". Retrieved on 2009-03-26. 
  8. ^ Nyk¨anen, Matti (October 26, 2007). "An Introduction to Functional Programming with the Programming Language Haskell". Retrieved on 2009-03-26. 

[edit] External links

Personal tools