Note first that if we want to count the number of multiples of a number ~ x ~ for numbers up to ~ M ~, we can use the following expression: ~ \big \lfloor \frac{M}{x} \big \rfloor ~

Note also that if we choose two numbers, say ~2~ and ~4~, where one is a multiple of the other, we get overlap. Because of this, let us choose only prime numbers.

Now, we use only prime numbers from ~1~ to ~N~. However, note that the following case:

6 3

yields 4 (2, 3, 4, 6) instead of our answer, which would be 5. This is because 6 overlaps, being a multiple of 2 and 3.

Now one might add a case for all multiples of two primes (semi-primes). However, consider the following case:

30 5

Our problem is that 30 is ~ 2 \times 3 \times 5 ~, which means that we add 30 three times from all the multiples, subtract it three times because of semi-prime duplicates, and then we don't include 30 as an option.

This prompts the following solution: Let ~x~ be the multiplicative sum of any group of primes. If the number of primes in the set is odd, we should add ~ \lfloor \frac{M}{x} \rfloor ~ to the total. If it is even, we should subtract it.

This idea is often called inclusion-exclusion, as we alternate between adding and removing totals because of overlap.

Let ~P~ be the number of primes less than ~N~. In total, we have to process ~ 2 ^ P ~ groups. However, note that if ~ N = 50 ~, ~ P = 15 ~, which is small enough to pass.

Time Complexity: ~ \mathcal O(P \times 2 ^ P) ~