How many positive integers less than 100 are that are NOT multiples of

Good solution, quick question, why at the end, with 7^2 you do not do -1, in terms of 100/49=2 and then you do not subtract 1 as you have been doing with the others?

-1 is done only where 100 is a multiple of that number for example 2,4,5, and not with 3 or 7.
Because when we divide 100/2 even 100 is included, but not in case of 100/49 as factors are only 49 and 98.

• Positive integers less than 100 -> [1,99] i.e., 99 numbers.
• Perfect squares greater than 1, whose multiples can be integers < 100 -> 4, 9, 16, 25, 36, 49, 64, 81

From the 99 total numbers (1 to 99), we need to exclude all multiples of the above 8 numbers.


(1) Multiples of 4 -> 4, 8, 12, ....96 -> \(\frac{(96-4)}{4}\) + 1 = 24 numbers.

(2) Multiples of 9 -> 9, 18, 27,....99 -> \(\frac{(99-9)}{9}\) + 1 = 11 numbers.

But here, we need to be careful. Those numbers which are multiples of 4 and 9 are getting counted twice. For instance, the number 36 is getting counted in (1) and (2).

To eliminate the double count, remove these numbers from either (1) or (2). These numbers are 36, 72.

(2) Unique multiples of 9 -> 11 - 2 (excluding 36, 72) = 9 numbers.

(3) Multiples of 16, 36, 64 -> already counted, because all multiples of 16, 36, and 64 are multiples of 4. No need to count these numbers again.

(4) Multiples of 25 -> 25, 50, 75 = 3 numbers.

(5) Multiples of 49 -> 49, 98 = 2 numbers.

(6) Multiples of 81 -> only 81, which has already been counted (as 81 is a multiple of 9). No need to again count this.

Total numbers in [1,99] that are multiples of a perfect square greater than 1 = 24 + 9 + 3 + 2 = 38 numbers.

So,

Total numbers in [1,99] that are NOT multiples of a perfect square greater than 1 = 99 - 38 = 61. Choice C.

---
Harsha