Most recent change of SieveOfEratosthenes

Edit made on February 27, 2009 by RiderOfGiraffes at 23:17:47

Deleted text in red / Inserted text in green

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.