Michael Bowen's VC Course Pages

Directions for Sieve of Eratosthenes

If you do not yet have one, please obtain a copy (print from the screen that comes up after you click this link) of the Sieve of Eratosthenes. The purpose of this procedure is to identify (and create a permanent list of) prime numbers, and to distinguish them from composite numbers. The steps are simple, but because they can be tedious, the procedure requires attention to detail. This is not recommended if you are not fully awake! Also, it's best to use pencil rather than pen, so you can easily correct mistakes.

Following the procedure below, you will circle some numbers; these are the primes. You will cross out other numbers with a large and clearly visible "X"; these are composites. If a number is either circled or crossed out, we will say that the number is "marked". If a number is neither circled nor crossed out, we will say that the number is "unmarked". The number 1, which is neither prime nor composite, may be marked with a star to indicate that it is special. So the number 1 is also considered "marked".

Are you (and your pencil) ready? Let's begin:

If you have not already done so, please draw a large star on the number 1 to indicate that it is neither prime nor composite.
Find and circle the smallest unmarked number on the sheet, to indicate that it is a prime. (The first time you do this, the smallest unmarked number will be 2.)
Draw a large X through all other multiples of the number you just circled (in this case, the multiples of 2, beginning with 4), to indicate that they are composite. If you do not wish to go all the way to the end of the sheet, you may stop at a smaller limit number, such as 200 or 300. However, if you wish to increase your limit number later, you will need to start with multiples of 2 again, and work your way up through the larger numbers.
After you have drawn an X through all the multiples, look for the smallest unmarked number remaining on the sheet, and circle it to indicate that it is prime. It is important not to circle any number that has already been marked with an X. In other words, each number should have only one type of mark (circle, X, or star).
Again draw a large X through all other multiples of the number you just circled, to indicate that they are composite. Some multiples will already have been marked with an X; if so, just skip that multiple and continue with the next multiple. For example, if you circled 3, you will notice that 6, 12, and 18 are already crossed out, so just go ahead and cross out 9, 15, 21, etc.
Repeat steps 4 and 5 as needed. The longer you work, the more numbers you will find that have already been crossed out. At some point (and for certain, no later than when you are working on multiples of 37), you will find that every multiple has already been crossed out in previous steps. This will happen sooner if you stopped marking after a smaller limit number such as 200 or 300. When you reach this point, you have successfully marked all the composite numbers; go on to the next step rather than repeating step 4 again.
Circle all the remaining unmarked numbers. However, if you stopped marking X's at a smaller limit number such as 200 or 300, then only circle the remaining unmarked numbers up to that limit number. (For example, if you stopped marking X's at 300, then do not circle any unmarked numbers past 300.)
If you have correctly followed the directions, you should now have a list (the circled numbers) of all prime numbers up to the limit number you selected. You can verify the first few prime numbers you've circled by checking them against the list printed near the bottom of the Divisibility Rules handout. Congratulations! You've just used the Sieve of Eratosthenes to find prime numbers all by yourself.

If you wish to return later and increase your limit number, first draw an X through the multiples of each prime already circled, up to your new limit (or, if you are ambitious, to the end of the sheet). When you have finished this, resume with step 4 above.