Sieve of Eratosthenes

From Wikipedia, the free encyclopedia

Sieve of Eratosthenes: algorithm steps for primes below 120 (including optimisation of starting at squares)

In mathematics, the Sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους) 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. None of his mathematical works survive, and the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.^[3]

[edit] The algorithm

A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself.

To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:

1. Create a list of consecutive numbers from two to n, (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Strike from the list all multiples of p less than or equal to n.
4. Find the first number remaining on the list greater than p (this number is the next prime); replace p with this number.
5. Repeat steps 3 and 4 until p² is greater than n.
6. All the remaining numbers on the list are prime.

[edit] Example

To find all the prime numbers less than or equal to 30, proceed as follows:

First generate a list of integers from 2 to 30:

  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

Strike (sift out) the multiples of 2 resulting in:

  2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

The first number in the list after 2 is 3; strike the multiples of 3 from the list to get:

  2  3     5     7          11    13          17    19          23    25          29

The first number in the list after 3 is 5; strike the remaining multiples of 5 from the list:

  2  3     5     7          11    13          17    19          23                29

The first number in the list after 5 is 7, but 7 squared is 49 which is greater than 30 so the
process is finished. The final list consists of all the prime numbers less than or equal to 30.

[edit] Algorithm complexity and implementation

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. When the Sieve of Eratosthenes is programmed for a computer, wheel factorization is often applied^{[citation needed]} before the sieve to increase the speed.

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

David Turner^[6] 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 ^[7] 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.

[edit] Mnemonic

A short, albeit imprecise, description of the Sieve or Erastosthenes in verse: ^[8][9]

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

[edit] Euler's Sieve

Euler in his Proof of the Euler product formula for the Riemann zeta function came up with a better version of the sieve of Eratosthenes in which each number was eliminated exactly once.

A) Start with all the natural numbers except '1' that is not a prime.
  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...
  ^
B) The leftmost number is prime. Multiply each number in the list by this prime and discard the products.
  2 3   5   7   9    11    13    15    17    19    21    23    25    27    29    31    33    35...
    ^
C) The number after the previous prime is also a prime. Multiply each number in the list starting from
   the latest prime by the latest prime and discard the products.
  2 3   5   7        11    13          17    19          23    25          29    31          35...
        ^
Repeat C) indefinitely. On each repetition a new prime is identified (marked ^) until all the primes in
the starting list have been found.

Comparing this algorithm with Euler's proof, the primes to the left of the cursor correspond to factors in the left hand side of the equation at each stage of the sifting, whereas the sequence to the right and including the cursor correspond to the series on the right hand side of the equation at each stage (minus the initial one).

When we have exceeded the square root of the upper limit of our range, we have the desired sequence of prime numbers. In the example given above that will be achieved when we identify the prime '7', to give our list of all primes less than 36.

[edit] See also

• Sieve theory
• Sieve of Atkin

[edit] References

[edit] External links

• Sieve of Eratosthenes in C
• Sieve of Eratosthenes in PHP
• Analyze the Sieve of Eratosthenes in an online Javascript IDE
• Interactive JavaScript Page
• Sieve of Eratosthenes by George Beck, Wolfram Demonstrations Project.
• Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.