SieveOfEratosthenes

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.

Last change to this page
Full Page history
Links to this page

Edit this page
(with sufficient authority)
Change password

Recent changes
All pages
Search