The Sieve of Eratosthenes
back

Here is a quick description of the Sieve of Eratosthenes
Let's say you want to list all the prime numbers up to N.
Write down the numbers 2,3,4,...,N, and perform the
following step repeatedly:

Circle the first uncircled number on the list and cross
off all multiples of that number.

Keep performing the test until the first uncircled number
on the list is at least the square root of N. Then stop and
circle all remaining numbers that have not been crossed off.
These are the primes less than N.

Why it works: Every composite number less than N
is a multiple of some prime that is less than the square
root of N. So, the above process crosses off all the
composite numbers. At the same time, the first uncircled
number on the list at any step is not divisible by any smaller
number and therefore is prime. So, exactly the composites
are crossed off and the primes are circled.