What is Sieve of Eratosthenes?
[[File:Sieve of Eratosthenes animation.gif|thumb|300px|Animation of the Sieve of Eratosthenes up to 120 (with the optimization of starting from squares). ]] The '''Sieve of [[Eratosthenes]]''' is a simple way to find ''all'' the [[prime number|prime numbers]] up to some number ''n'': # Write all the numbers from 2 up to ''n'' onto a piece of paper, in order. We will perform the following steps so that all the non-prime numbers will be crossed out, and what's left will be the primes. # Choose the first, i.e. the smallest ''available'' number. Call it ''p'' (it will be 2 at the start). If there's no more available numbers, stop. # Count up from ''p'' as ''2p, 3p, 4p, ...,'' up to ''n'' in steps of ''p'', and cross out each of those numbers. Some numbers will be already crossed out, that's okay. Do not cross out the number ''p'' itself but consider it no longer ''available''. # Go back to step 2. When the algorithm is finished all the numbers that are left not crossed out are all the prime numbers from 2 up to ''n''. As an optimization we can start the counting in step 3 from ''p<sup>2</sup>'', and stop in step 2 when ''p<sup>2</sup>'' is greater than ''n''. This is allowed because for each number ''k'' that is smaller than ''p'', the number ''kp'' in step 3 will be already crossed out as part of the algorithm working for some previous prime that is smaller than ''p'' – the smallest such prime which divides ''k'' evenly. [[Category:Number theory]] {{math-stub}}