From Wikipedia, the free encyclopedia

In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. It is the predecessor to the modern Sieve of Atkin, which is faster but more complex. It was created by Eratosthenes, an ancient Greek mathematician. Wheel factorization is often applied on the list of integers to be checked for primality, before Sieve of Eratosthenes is used, to increase the speed.

Contents 1 Algorithm 2 Pseudocode 3 References 4 External links

1. Write a list of numbers from 2 to the largest number you want to test for primality. Call this List A. (This is the list of squares on the left-hand-side of the picture.)
2. Write the number 2, the first prime number, in another list for primes found. Call this List B. (This is the list on the right-hand-side of the picture.)
3. Strike off 2 and all multiples of 2 from List A.
4. The first remaining number in the list is a prime number. Write this number into List B.
5. Strike off this number and all multiples of this number from List A. The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps.
6. Repeat steps 4 through 6 until no more numbers are left in List A.

The following is pseudocode for the algorithm:

// arbitrary search limit
limit ← 1.000.000                   

// assume all numbers are prime at first
is_prime(i) ← true, i ∈ [2, limit] 

for n in [2, √limit]:
    if is_prime(n):
        // eliminate multiples of each prime,
        // starting with its square
        is_prime(i) ← false, i ∈ {n², n²+n, n²+2n, ..., limit}

for n in [2, limit]:
    if is_prime(n): print n

Or, more simplified:

limit = 1000000
sieve$ = string of the character "P" with length limit

prime = 2
repeat while prime2 < limit
    set the character at the index of each multiple of prime (excluding index prime * 1) in sieve$ to "N"
    prime = index of the next instance of "P" in sieve$ after index prime
end repeat

print the index of each instance of "P" in sieve$

Κοσκινον Ερατοσθενους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.

For more advanced developments, see:

• Sieve of Atkin
• Primality test
• General number field sieve
• Sieve theory

• Analyze the Sieve of Eratosthenes in an online Javascript IDE
• Eric W. Weisstein, Sieve of Eratosthenes at MathWorld.
• Interactive animation (JavaScript required)
• Sieve of Eratosthenes at cut-the-knot