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
• 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 $p^2$ and starting from there, cross out every $p^{th}$ number
• Repeat the last step until the square is larger than n
All the remaining uncrossed numbers are also prime numbers.

Note that this procedure does not use division.

(none) (none) (none)
Eratosthenes (none)

## You are here

SieveOfEratosthenes