## Prime-looking numbers

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.  