Given a list of all composite numbers below 1000, how many will remain after erasure of numbers divisible by 2,3 or 5?

Rem1: "or" is inclusive i.e. and/or.
Rem2: number 1 is neither prime nor composite, so it does not appear on the initial list.

Method 1:  Look up the number of primes below 1000:  π(1000)=168
So there are 999-168 composites
subtract the 499 multiples of 2 (not counting 2)
subtract the 332 multiples of 3 (not counting 3)
subtract the 199 multiples of 5 (not counting 5)
add back the over-counts:
166 multiples of 6
100 multiples of 10
66 multiples of 15
re-subtract the 33 multiples of 30 (which got added back once too many)
and we get 100.

Method 2:  Count them
Make a list of the 31 primes from 7 to 139.
7 times each of them is under 1000 (31 in all)
11 times each from 11 to 89 is under 1000 (20 more)
13 times each from 13 to 73 is under 1000 (16 more)
17 times each from 17 to 53 is under 1000 (10 more)
19 times each from 19 to 47 is under 1000 (8 more)
23 times each from 23 to 23 is under 1000 (6 more)
29 times both from 29 to 31 is under 1000 (2 more)
31 times 31 is under 1000 (1 more)
49 times each from 7 to 19 is under 1000 (5 more)
Plus one more for 7*11*11
Gives a grand total of 100.

I'm not sure which method was easier but it was very satisfying when they came out the same and even more so when Charlie got the same thing!

Posted by Jer on 2015-02-18 22:56:24