Tough-to-test composites

Let $M_2$ , $M_3$ , and $M_5$ be the sets of integer multiples of $2$ , $3$ , and $5$ , respectively, between $1$ and $1000$ , inclusive.

$|M_2|=500$

$|M_3|=333$

$|M_5|=200$

$|M_2\cap M_3|=166$

$|M_2\cap M_5|=100$

$|M_3\cap M_5|=66$

$|M_2\cap M_3\cap M_5|=33$

By PIE ,

$\begin{aligned} |M_2\cup M_3\cup M_5|&=|M_2|+|M_3|+|M_5|-|M_2\cap M_3|-|M_2\cap M_5|-|M_3\cap M_5|+|M_2\cap M_3\cap M_5| \\ &=500+333+200-166-100-66+33 \\ &=734 \end{aligned}$

By De Morgan's Laws , the number of integers between $2$ and $1000$ inclusive that are not multiples of $2$ , nor $3$ , nor $5$ is $999-734=265$ ( $1$ is excluded because it is neither prime nor composite).

It is given that there are $168$ prime numbers between $1$ and $1000$ inclusive. Excluding $2$ , $3$ , and $5$ , there are $165$ prime numbers. Therefore, the number of tough-to-test composite numbers is: $265-165=\boxed{100}$ .