Sieve of Eratosthenes

related topics
{math, number, function}
{god, call, give}
{rate, high, increase}

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. However, none of his mathematical works survived—the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.[3]

Contents

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:

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.

The complexity of the algorithm is O(n(logn)(loglogn)) bit operations with a memory requirement of O(n).[4] Time complexity in RAM machine model is O(nloglogn) operations; this is a direct consequence of the fact that the prime harmonic series asymptotically approaches 1/(ln(ln(N))). The segmented version of the sieve of Eratosthenes, with basic optimizations, uses O(n) operations and O(n1 / 2loglogn / logn) bits of memory.[5]

David Turner suggested in 1975 that the primes sieve could be represented in a strikingly simple and elegant way in purely functional programming languages.[6] Turner's sieve, which is more closely related to the Euler's sieve below, rendered in Haskell, is:

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

In 2008, Melissa O'Neill showed that the complexity of Turner's algorithm is significantly worse than the complexity of the classic imperative renditions of the sieve.[7] O'Neill demonstrated a priority queue based rendition of the sieve of Eratosthenes in Haskell with complexity similar to that of the classic imperative implementations.

[edit] Mnemonic

A short, albeit imprecise, description of the Sieve of Eratosthenes in verse:

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

—Traditional, [8][9]

[edit] Euler's sieve

Euler in his Proof of the Euler product formula for the Riemann zeta function came up with a version of the sieve of Eratosthenes, better in the sense that each number was eliminated exactly once. Unlike Eratosthenes' sieve which strikes off multiples of primes it finds from the same sequence, Euler's sieve works on sequences progressively culled from multiples of the preceding primes:

Full article ▸

related documents
Co-NP
Ring homomorphism
Equivalence class
Endomorphism ring
Center (group theory)
Sedenion
Measurable function
Disjoint sets
Identity function
Context-sensitive language
Galois group
Markov process
Church–Rosser theorem
Co-NP-complete
Euclidean distance
Chart parser
Lazy initialization
Power associativity
Prime ideal
Digital Signature Algorithm
Almost all
Gabriel Lamé
Leaf node
JUnit
Senary
Recursive language
Harmonic analysis
Water, gas, and electricity
Mary (programming language)
Uniform Resource Locator