# Positive integers NOT divisible by 3 or more primes

How many positive integers $<200$ are NOT divisible by 3 or more primes ?

\begin{eqnarray*} &=&\text{Number of positive integers less than }200-\text{ Number of composite integers less than $200$ having at least 3 different prime factors}\\ &=&199-\Bigg(\left\lfloor\frac{199}{lcm(2,3,5)}\right\rfloor+\left\lfloor\frac{199}{lcm(2,3,7)}\right\rfloor+\left\lfloor\frac{199}{lcm(2,3,11)}\right\rfloor+\left\lfloor\frac{199}{lcm(2,3,13)}\right\rfloor\\&&+\,\left\lfloor\frac{199}{lcm(2,3,17)}\right\rfloor+\left\lfloor\frac{199}{lcm(2,3,19)}\right\rfloor+\left\lfloor\frac{199}{lcm(2,3,23)}\right\rfloor+\left\lfloor\frac{199}{lcm(2,3,29)}\right\rfloor\\&&+\,\left\lfloor\frac{199}{lcm(2,3,31)}\right\rfloor+\left\lfloor\frac{199}{lcm(3,5,7)}\right\rfloor+\left\lfloor\frac{199}{lcm(3,5,11)}\right\rfloor+\left\lfloor\frac{199}{lcm(3,5,13)}\right\rfloor\Bigg)\\ &=&199-(6+4+3+2+8*1)\\ &=&199-23\\ &=&176 \end{eqnarray*} I did NOT count composite integers having more than 3 different prime factors because i thought they should be multiples of composite integers having exactly 3 different prime factors and counting them would result in an overcount.

However, the answer given in the book is $168$.

What is wrong in my answer ?

• You would have subtracted the ones divisible by four or more primes more than once. The lowest such number is $210$, which is not in your range, but if it were you would have to add it back in once. This is the [inclusion-exclusion principle]( en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle) Commented Dec 11, 2014 at 14:43

You forgot the multiples of $\operatorname{lcm}(2,5,7)$, $\operatorname{lcm}(2,5,11)$, $\operatorname{lcm}(2,5,13)$, $\operatorname{lcm}(2,5,17)$, $\operatorname{lcm}(2,5,19)$, $\operatorname{lcm}(2,7,11)$, and $\operatorname{lcm}(2,7,13)$, which make a difference of
$$1\cdot 2 + 6\cdot 1 = 8 = 176 - 168.$$