Sieve of Eratosthenes From Wikipedia, the free encyclopedia You have new messages (last change). Jump to: navigation, search Sieve of Eratosthenes

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 the Sieve of Eratosthenes is used, to increase the speed. Contents [hide]

   * 1 Algorithm
   * 2 Complexity
   * 3 Mnemonic
   * 4 See also
   * 5 References
   * 6 Sources
   * 7 External links

[edit] Algorithm

  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 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 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 and 5 until no more numbers are left in List A. Note that, once you reach a number greater than the square root of the highest number in List A, all the numbers remaining in List A are prime.

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$

[edit] Complexity

The complexity of the algorithm is O((nlogn)(loglogn)) and has a memory requirement of O(n).[1]

[edit] Mnemonic

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

Sift the Two's and sift the Three's, The Sieve of Eratosthenes. When the multiples sublime, The numbers that remain are Prime.

[edit] See also

   * Primality test
   * General number field sieve
   * Sieve theory

[edit] References

  1. ^ Pritchard, Paul Linear prime-number sieves: a family tree. Sci. Comput. Programming 9 (1987), no. 1, 17--35.
  2. ^ William F. Clocksin and Christopher S. Mellish. Programming in PROLOG. Springer-Verlag.

[edit] Sources

   * Κοσκινον Ερατοσθενους 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.

[edit] External links

   * Analyze the Sieve of Eratosthenes in an online Javascript IDE
   * Interactive JavaScript Applet
   * Sieve of Eratosthenes by George Beck, The Wolfram Demonstrations Project.

[hide] v • d • e Number-theoretic algorithms Primality tests AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division Sieving algorithms Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm Other algorithms Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests. Retrieved from "http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" Categories: Primality tests | Articles with example pseudocode Views

   * Article
   * Discussion
   * Edit this page
   * History
   * Watch

Personal tools

   * Sulbahri
   * My talk
   * My preferences
   * My watchlist
   * My contributions
   * Log out

Navigation

   * Main Page
   * Contents
   * Featured content
   * Current events
   * Random article

Interaction

   * About Wikipedia
   * Community portal
   * Recent changes
   * Contact Wikipedia
   * Donate to Wikipedia
   * Help

Search

Toolbox

   * What links here
   * Related changes
   * Upload file
   * Special pages
   * Printable version
   * Permanent link
   * Cite this page

Languages

   * Български
   * Català
   * Česky
   * Deutsch
   * Español
   * Esperanto
   * Français
   * 한국어
   * Hrvatski
   * Bahasa Indonesia
   * Italiano
   * עברית
   * ქართული
   * Lietuvių
   * Magyar
   * Македонски
   * Nederlands
   * 日本語
   * ‪Norsk (bokmål)‬
   * Polski
   * Português
   * Română
   * Русский
   * Sicilianu
   * Simple English
   * Slovenčina
   * Slovenščina
   * Српски / Srpski
   * Suomi
   * Svenska
   * Türkçe
   * Українська
   * 中文

Powered by MediaWiki Wikimedia Foundation

   * This page was last modified on 6 April 2008, at 14:06.
   * All text is available under the terms of the GNU Free Documentation License. (See Copyrights for details.)
     Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a U.S. registered 501(c)(3) tax-deductible nonprofit charity.
   * Privacy policy
   * About Wikipedia
   * Disclaimers