skip to main content
Michael Bowen's VC Course Pages

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:

  1. 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.
  2. 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.)
  3. 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.
  4. 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).
  5. 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.
  6. 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.
  7. 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.)
  8. 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.


http://academic.venturacollege.edu/mbowen/courses/handouts/h_eratosthenes.shtml

Michael Bowen's VC Course Pages: Directions for Sieve of Eratosthenes

Last modified: Sunday 06 August 2017 22:19:03
Created by Michael Bowen (Professor of Mathematics)
Department of Mathematics, Ventura College, California, USA
Ventura College is an independent college within the Ventura County Community College District.
Please email comments, questions, suggestions, or a notification if you find a "broken" link.
As an alternative, you may leave a voice message at (805) 289–6256.

User agents known to render this document correctly include:

Trademarks: Adobe®, Acrobat®, Macromedia®, and Shockwave® are registered trademarks, and Acrobat Reader™ is a trademark, of Adobe Systems Incorporated in the United States and/or other countries. Macintosh® is a registered trademark, and Safari™ is a trademark, of Apple, Inc. Borland® is a registered trademark of Borland Software Corporation in the United States and other countries. This web page is an independent publication and has not been authorized, sponsored, or otherwise approved by Borland Software Corporation. Corel® and WordPerfect® are registered trademarks of Corel Corporation. The buttons, name, and corporate logo (the "CC" in a circle) of Creative Commons™ are trademarks of Creative Commons. NoteTab™ is a trademark of Fookes Software. Zip® is a registered trademark of Iomega Corporation in the United States and/or other countries. Microsoft®, Visual C++®, Visual Studio®, and Windows® are registered trademarks of Microsoft Corporation. Firefox® is a registered trademark of the Mozilla Foundation. Netscape® and Mozilla® are registered trademarks of Netscape Communications Corporation. UNIX® is a registered trademark of The Open Group. Opera Software™ is a trademark of Opera Software ASA. Oracle® and Java® are registered trademarks of Oracle and/or its affiliates. Norton AntiVirus® is a registered trademark of Symantec Corporation. Maple™ is a trademark of Waterloo Maple Inc. World Wide Web Consortium® and W3C® are registered trademarks, and Amaya™ and XHTML™ are trademarks, of the World Wide Web Consortium. All other trademarks and service marks are the property of their respective owners.

Copyrights: The orange-and-black scales-of-justice logo is in the public domain. Opera browser copyright © by Opera Software ASA. Ventura College pirate logos and "Set Your Course" logos copyright © by the Ventura County Community College District. W3C logos copyright © by the World Wide Web Consortium. WAVE copyright © 2014 by WebAIM. Remainder of page copyright © 2005–2017 by Michael Bowen. All rights reserved.

Creative Commons License

Michael Bowen's Ventura College Course Pages are licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License - external link . You are also bound by this site's Terms of Use.


Ventura College 'Set Your Course' logo
Click to return to the top of this page View the terms of use View the CSS validator home page View the W3C Validator home page View the Web Accessibility Evaluation Tool (WAVE) home page