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.