Edit made on February 27, 2009 by RiderOfGiraffes at 23:17:47
Deleted text in red
/
Inserted text in green
WW
HEADERS_END
Eratosthenes, an ancient Greek Mathematician, developed a simple algorithm for finding prime numbers less than a desired number.
* Draw a table of all numbers less than the desired number n
* Draw a circle around the number 2 and
** Square 2 giving 4, then starting at 4, cross out all the multiples of 2. every second number
* Circle the next number not crossed out (this is a prime number) - and call it "p"
** Square p, giving EQN:p^2 and starting from there, cross out all the multiples of this every EQN:p^{th} number
* Repeat the last step until you have circled a number greater than the square root of is larger than n
All the remaining uncrossed numbers are also prime numbers.