## 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.