8. [7] How many integers between 2 and 100 inclusive cannot be written as $m \cdot n$, where $m$ and $n$ have no common factors and neither $m$ nor $n$ is equal to 1 ? Note that there are 25 primes less than 100 .
Answer: 35 A number cannot be written in the given form if and only if it is a power of a prime. We can see this by considering the prime factorization. Suppose that $k=p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{n}^{e_{n}}$, with $p_{1}, \ldots, p_{n}$ primes. Then we can write $m=p_{1}^{e_{1}}$ and $n=p_{2}^{e_{2}} \cdots p_{n}^{e_{n}}$. So, we want to find the powers of primes that are less than or equal to 100 . There are 25 primes, as given in the problem statement. The squares of primes are $2^{2}, 3^{2}, 5^{2}, 7^{2}$. The cubes of primes are $2^{3}, 3^{3}$. The fourth powers of primes are $2^{4}, 3^{4}$. The fifth powers of primes are $2^{5}$, The sixth powers of primes are $2^{6}$. There are no seventh or higher powers of primes between 2 and 100. This adds 10 non-primes to the list, so that in total there are $10+25=35$ such integers.