February 19, 1997
This document is also available in the following formats:
To print out this document in the Computer Lab it is best to use the PostScript version. After you click on PostScript a Ghostview window should appear. Hold the left mouse button on FILE and then release on PRINT. Then click on OK. A copy should arrive shortly at the printer near the door.The Sieve of Eratosthenes is a method for finding all prime numbers less than or equal to a specified integer n>1. It is based on the following theorem from the notes:
Theorem.
An integer n>1 is prime iff it has no prime divisor p with 
.
Suppose we wish to find all prime numbers less than or equal to 100.
By the theorem, any composite number less than or equal to 100
must have a prime divisor less than or equal to 
.
The primes less than or equal to 10 are 2, 3, 5 and 7.
Hence, from a list of the integers from 2 to 100 we delete all the
multiples of 2, all multiples of 3, all multiples of 5 and all
multiples of 7 (not including 2, 3, 5 and 7 themselves).
Try this now:
Note that all multiples that were deleted are clearly composite. Any number remaining on the list is not divisible not divisible by 2, 3, 5 and 7 (except 2, 3, 5 and 7 themselves). Hence the remaining numbers in the list are prime. These are boxed in the list below. The composite numbers have been sieved out of the list.
Now find all primes less than 200.
