Sieve of Eratosthenes: Wikis

Advertisements
  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

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. 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:

  1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n),
  2. Initially, let p equal 2, the first prime number,
  3. While enumerating all multiples of p starting from p2, strike them off from the original list,
  4. Find the first number remaining on the list after p (it's the next prime); let p equal this number,
  5. Repeat steps 3 and 4 until p2 is greater than n.
  6. All the remaining numbers in the list are prime.
Advertisements

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 out the multiples of 2 from the original list starting from 4, 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 out the multiples of 3 from the
original list starting from 9, to get:

  2  3     5     7          11    13          17    19          23    25          29

The first number in the list after 3 is 5; strike out the multiples of 5 from the
original list starting from 25:

  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.

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. 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]

Recently, 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.

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]

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:

A) Start with all the natural numbers except '1' which 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 ...
  ^

B) The leftmost number is prime. Multiply each number in the list by this prime and
   then discard the products:

 (4 6 8 10 12 14 16 18 20 22 24 26 28 30 ... )

  These are removed:
      4   6   8   10    12    14    16    18    20    22    24    26    28    30 

  These are left:
  2 3   5   7   9    11    13    15    17    19    21    23    25    27    29 ...
    ^

C) The number after the previous prime is also a prime. Multiply by it each number 
   in the new list starting from this prime and then discard the products:

   (9   15  21  27   33    39    45    51    57    63    69    75    81    87 ...)

  These are removed:
                9                15                21                27 

  These are left:
  2 3   5   7        11    13          17    19          23    25          29 ...
        ^

Repeat C) indefinitely. On each repetition a new prime is identified (marked by the cursor, ^) until all the primes in the starting list have been found.

Euler's sieve is thus naturally well suited to generating infinite sequences of prime numbers and Turner's sieve is a close rendition of it. Expressed in Haskell, it is:

 import Data.OrdList (minus)
 
 primes = euler [2..]
 euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs))

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 generating only a finite sequence of primes, 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 or equal to 30.

See also

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", http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes, references 16. November 2008.
  3. ^ Nicomachus, Introduction to Arithmetic, I, 13. [1]
  4. ^ Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci. Comput. Programming 9:1 (1987), pp. 17–35.
  5. ^ A. O. L. Atkin and D. J. Bernstein, "Prime sieves using binary quadratic forms", Mathematics of Computation 73 (2004), pp. 1023–1030.
  6. ^ Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975.
  7. ^ 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.
  8. ^ Merritt, Doug (December 14, 2008). "Sieve Of Eratosthenes". http://c2.com/cgi/wiki?SieveOfEratosthenes. Retrieved 2009-03-26. 
  9. ^ Nyk¨anen, Matti (October 26, 2007). "An Introduction to Functional Programming with the Programming Language Haskell". http://www.cs.uku.fi/~mnykanen/FOH/lectures.pdf. Retrieved 2009-03-26. 

External links


Simple English

, which is faster but more complex.]] The Sieve of Eratosthenes is a simple test to check if a number is a prime number.

If someone wants to check for a certain number n to be prime, they do as follows:

  • Write numbers from 2 to that number onto a piece of paper.

Do the following:

  1. Get the next number that is not crossed out.
  2. Cross out all multiples of that number on your sheet.

Repeat this for all numbers until you reach the square root of n.

If n has been crossed out it is not prime.


Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message