The Sieve of Eratosthenes
Not all numbers are hard to identify as prime or composite (not prime). For example, any even number larger than 2 is composite. However, while some numbers can be easy to classify, others can be extremely difficult. Fortunately, there are some tricks that can help, at least under some circumstances. One such trick is the Sieve of Eratosthenes. Although The Sieve saves work in a number of ways, where it really shines is in making lists of prime numbers. But perhaps the best thing about the Sieve of Eratosthenes isn’t actually its utility as a prime-number finding trick, so much as its value in prompting curious people to start asking questions about numbers. It’s been doing that for a long, long time…
Eratosthenes of Cyrene
Eratosthenes lived from 276 BCE to 194 BCE. He was a director of the Library at Alexandria and wrote a number of significant ancient treatises. He also corresponded with Archimedes, from whom he was the recipient of the important letter, The Method, in which Archimedes revealed the line of reasoning that he used when he thought of some of the amazing things he did.
Eratosthenes with Alexandrian Scholars — Nobody knows what the Library at Alexandria looked like, but this artist’s conception includes sculptures based on colossal statues found by divers in the underwater ruins of the city.
You may have heard that long before Christopher Columbus, the ancient Greeks knew that the earth was round. But their knowledge was much more than merely knowing the shape: Eratosthenes calculated the actual size of the earth too, and he did it to an accuracy of within 50 miles!
Eratosthenes & Prime Numbers
Back then, just as now, mathematicians were fascinated with prime numbers. In order to develop theories about them, it was useful to make lists of which numbers were prime, and which were composite. Here, finally, is the ingenious technique Eratosthenes developed to do just that:
How to make a Sieve of Eratosthenes
- Download and print a worksheet. We recommend you use the one which lists all the whole numbers from 2 to 100. If you are a teacher trying to work with a limited time slot, you might want a smaller sheet with the numbers from 2 to 50. Both worksheets have a place next to each number for marking it as either composite or prime.
- Find the next unmarked number. Initially that will be 2. You’ll come back to this step later and use 3, then 5, etc.
- Mark that next unmarked number as prime. In our example, we wrote a “p” with red pencil. We used red pencil for primes to make them stand out in the completed worksheet.
Use red to mark the next unmarked number as a prime.
- Mark all multiples of that number as composite until you get to the end of your worksheet. In our example, we wrote a “c” with regular pencil. For example, multiples of 2 are 4, 6, 8, 10, etc.; the multiples of 3 are 6, 9, 12, 15, etc. If a number is already marked as composite, you don’t have to mark it again. If you don’t want to multiply, you can just “count by” the number. When you get into the bigger numbers, you can add to find the multiples. For example after you mark 13 as prime, add 13 to 13 to get 26 (we would mark 26 as composite, but it was already marked when we did the 2s); then add 13 to 26 to get 39 (we already marked 39 as composite when doing the 3s); then add 13 to 39 to get 52 (we already marked 52 as composite when doing the 2s) etc.
Mark all the multiples of the prime as composite.
- Repeat steps 2 through 4 until all numbers are marked as prime or composite.
Repeat with the next number, 3 in this example.
Taking Short Cuts
Most people soon want to start taking short cuts. Is it OK to take short cuts? It depends on the short cut! If you know your idea will work, then, of course it’s OK. If you’re not sure that your idea is right, it is extremely valuable to spend some time thinking about it. In fact, spending time thinking about whether certain short cuts will work is one of the best ways to learn from this activity.
Wondering About Prime Numbers
You are also likely to start wondering some things about prime numbers. We’ll resist the temptation to try to answer all the common questions here, because it’s best for students to wonder about them a bit, but here are two of them. Yes — the bigger the numbers get, the scarcer prime numbers get. But also, no matter how big the numbers get, the prime numbers never run out — there’s always a bigger prime number out there somewhere.
Next Topic: Prime Numbers & Composite Numbers
About this Bubbly Primes Math Help Page
*It is not certain exactly how accurate Eratosthenes’s calculations were. Our source for the 50 mile estimate is: Calculus With Analytic Geometry by George Simmons, McGraw-Hill 1985, page 727.
Speaking of books, you may be interested in a kids’ book about Eratosthenes called, The Librarian Who Measured The World, by Kathryn Lasky.
