Fallout from the Sieve of Eratosthenes - Combinatorial Activity for Counting Primes

BACKGROUND and OVERVIEW of ACTIVITY
Middle schoolers are often introduced to the famous sieve mentioned in the title to find which numbers, say from 1 to 100, are prime. This is a common activity in which all the multiples of 2 are first crossed out, then multiples of 3 and so on. The following is a combinatorial (counting) activity that may help them (and more advanced learners as well) appreciate just how beautiful this method is and how it can be generalized to demonstrate the endlessness of primes. In the process, middle schoolers will review the concepts of multiples, common multiples as well as composite vs. prime numbers. The 2nd activity below is for upper-level students although middle schoolers can certainly try it.

Consider the first 3 primes; 2, 3, and 5. Children know what the next one is and that there are many more after that up to 30, but, for this activity, tell them that they will find, by elimination, the remaining primes up to 30. Specifically, using the famous sieve algorithm, they will determine there are SEVEN more primes up to 30 by eliminating all the numbers that are divisible by 2, 3 or 5! Sounds like you've seen this many times? Wait...

Note: DO NOT have students use colored markers or pens to cross out numbers. It tends to obliterate the marks underneath that are needed for analysis.

Middle School Activity (standard sieve approach):
1. List the positive integers up to and including 30.
2. Cross out the multiples of 2 in your list using a slanted /. Explain how you could have determined that 15 numbers were crossed out without using your list.
3. Now cross out all the multiples of 3 from the original list using the \ mark. How many numbers did you cross out this time? How could you have determined this without your list? Count how many numbers have been crossed out twice. How could you have determined this without your list?
Note: In some applications of the Sieve method, students cross out only from the remaining numbers, not from the original list each time. Since our objectives here involve developing the idea of common multiples and also combinatorial methods, students are instructed to cross out some numbers more than once. This is not unusual in many texts or workbooks.
4. Now cross out all the multiples of 5 from the original list. Use the --- mark for this. How many numbers were crossed out? How could you have determined this without your list?
5. Count how many numbers were crossed out exactly once. Describe these numbers.
Note: Students may have difficult expressing this and some discussion is needed. For example, they might at first say "Numbers divisible by only two." This is a fine response but how can the instructor build on this?
6. Count how many numbers were crossed out exactly twice. Describe these numbers.
7. Explain why there was only one number crossed out exactly 3 times.
8. There should now be EIGHT numbers remaining which have not been crossed out. Are these numbers all prime?
9. Ask more questions!

Notes: We know that students (of all ages!) have difficulty with the issue of the number 1 not being regarded as prime. The accepted definition of prime requires that the number have exactly two distinct factors. Seems arbitrary, huh? Besides 1, most students will assume that the remaining seven numbers necessarily have to be prime, however this method does not guarantee that! If we used the above sieve up to 50, then 49 would be left over as well! Subtle...

OVERVIEW OF ADVANCED ACTIVITY
How could older students have attacked this without making a list, using more sophisticated combinatorial methods? The idea behind the above activity was to first identify the numbers that were divisible by 2, 3, OR 5. After eliminating these and the number 1, students were to consider the remaining numbers, which all happen to be prime. The remaining part of this activity deals with combinatorial methods needed to COUNT how many numbers are divisible by 2, 3 or 5 without first making a list. Some will still need to make the list!

MORE ADVANCED ACTIVITY
Consider the list of the positive integers up to and including 30. The following set of questions is designed to get an accurate count of the numbers that are multiples of 2, 3 or 5 and then to consider the remaining numbers.
1. Explain why there are 15 multiples of 2 in this list without actually counting or listing them!
2. Explain why there are 10 multiples of 3 in the original list without...
3. Explain why there are 6 multiples of 5 in the original list without ...
4. Thus far we appear to have accounted for 15+10+6 = 31 numbers in this list which are multiples of 2, 3 or 5. Since there are only 30 numbers to start with, what went wrong! Explain carefully.
Note: The method of 'overcounting' is a critical one for many set-theoretic and counting problems.
5. By now you realize that we need to compensate for the numbers that were counted more than once. Show that 10 numbers were counted more than once.
6. To compensate for these duplications, we can adjust the count: 31 - 10 = 21. Thus it appears that there are 21 numbers in our list that are divisible by 2, 3 or 5. In fact, there are 22! What went wrong! [If you don't believe this, make a list and count!!].
Note: This is subtle. The number 30 still needs to be counted.
7. Ok, we have hopefully established that there are 22 numbers that need to be eliminated from our original list of 30. Thus, there are 30 - 22 = 8 numbers remaining. One of these 8 is not prime. Which one?
8. If you haven't already done so, make a list of the 30 numbers and actually work through each of the steps above to verify your results.
9. What do you think? Is this a good method for counting how many primes there are in a particular list? Would it be practical for counting how many primes there are up to, say, 210 given that 2, 3, 5 and 7 are prime? Where did 210 come from? Why might this method fail to produce only primes?

Summary Comments:
Although this post seemed to be about a sieve for primes, you've probably figured out that it really became an activity to solve the problem of counting how many of the 30 numbers in the list were not divisible by 2, 3 or 5. I'm sure you are thinking that there are many others ways we could have counted the multiples of 2, 3 or 5. Your students may object to the above method and suggest a 'better' one. For example, count all the even numbers up to 30 first. Then count the odd multiples of 3, then the powers of 5 . No duplications, short and sweet, right? However, the set-theoretic method of counting with duplications, then compensating is actually more powerful and can be generalized to longer lists of primes. Embedded in this activity is the subtle notion that there cannot be a finite number of primes. Do you think students would recognize that on their own?