Prime-looking numbers
Task number: 3488
We will say that a number is prime-looking if is composite but is not divisible by 2, 3 or 5. The three smallest prime-looking numbers are 49, 77 and 91.
We know that there are 168 primes smaller than 1000. How many prime-looking numbers are there smaller than 1000?
Solution
There are \(499\) numbers smaller than \(1000\) that are divisible by two.
Further \(333\) divisible by three, \(199\) divisible by \(5\), \(166\) divisible by \(6 = 2{\cdot} 3\), \(99\) divsible by \(10 = 2{\cdot} 5\), \(66\) divisible by \(15 = 3{\cdot} 5\) and finally \(33\) divisible by \(30 = 2{\cdot} 3\cdot 5\).
So using the inclusion-exclusion principle we have \[499 + 333 + 199 - 166 - 99 - 66 + 33 = 733\] numbers that cannot be prime-looking, because these numbers are divisble by \(2,\ 3\) or \(5\) – including these prime numbers themselves.
So we are left with \(999 - 733 = 266\) numbers. But they are not all prime-looking, because some of them are actually prime! According to the assignment there are \(168\) prime numbers less than \(1000\), of which we must omit \(2{,}3,5\), which we already subtracted earlier. However we must still subtract 1, because it is neither prime nor composite. So we obtain \( 266 - 166 = 100\) in all.
Answer
There are 100 prime-looking numbers less than 1000.
