An AMC problem on sieveing primes

The following is an AMC 12 problem from 2005, courtesy of the MAA Minute Math. Follow the link for an interactive version complete with hints, solutions and difficulty hosted on MAA.org.

Problem: Call a number “prime-looking” if it is composite but not divisible by 2, 3 or 5. The three smallest prime-looking numbers are 49, 77 and 91. There are 168 prime numbers less than 1000. How many prime-looking numbers are there less than 1000?

Solution: This is really a combinatorics problem masquerading as number theory. We sieve out those numbers divisible by 2, 3 and 5, using the principle of inclusion and exclusion.
[tex]\lfloor \frac{999}{2} \rfloor + \lfloor \frac{999}{3} \rfloor+\lfloor \frac{999}{5} \rfloor-\lfloor \frac{999}{6}\rfloor-\lfloor \frac{999}{10}\rfloor-\lfloor \frac{999}{15}\rfloor+\lfloor \frac{999}{30}\rfloor[/tex]
=733 numbers that are divisible by 2, 3 or 5. Subtract this from 999 to get 266 possible prime-looking numbers. But among these are the other 165 primes (between 7 and 999). Before we write down the answer, remember to remove the number 1. Hence the answer is exactly 100.

This entry was posted in Combinatorics, Number Theory, Problems. Bookmark the permalink.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>