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 cross out all the multiples of 2.
* Circle the next number not crossed out (this is a prime number) - cross out all the multiples of this number
* Repeat the last step until you have circled a number greater than the square root of n
* Draw a circle around the number 2
** Square 2 giving 4, then starting at 4, cross out 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 every EQN:p^{th} number
* Repeat the last step until the square is larger than n
All the remaining uncrossed numbers are also prime numbers.