Let's use n=5 and let count(i) be the number of multiples of i in the range L <= r <= R

Naively count the multiples of the 2,3,5

ans += count(2) + count(3) + count(5)

Now, subtract the multiples of the numbers that you counted twice (the numbers that have at least 2 primes as divisors)

ans -= count(2*3) + count(2*5) + count(3*5)

Now, for 2*3*5, you counted these numbers 3 times in the first step and subtracted 3 times in the second step so you just need to do:

ans += count(2*3*5)

More generally, you will take every number that is the product of some number of primes lesser or equal to n (at least 1 prime) and if there is an odd number of primes, you add. If there is an even number of primes, you subtract. The complexity will be O(2^number_of_primes_until(n)) since count(i) is constant.

Edit: sorry, it isn't as simple as subtract/add but the thought is this.

Use principle of inclusion and exclusion. Key observations are:

• There are only 15 prime numbers less than 50(max** N** value)

• Let count(A) be the count of numbers between L and R such that numbers are divisible by that prime number A.

• You basically want to find the value of expression count(2 U 3 U .... U last prime number(<=n)), The U is the union operator.

• The expression above means that you want to calculate numbers between L and** R** such that numbers are divisible by at least one of those prime numbers, which is basically the principle of inclusion and exclusion

• Using the above, you have max of 2^15 subsets of calculations that you have to do. Each of which will require O(1) time, since it will require just two divisions and a subtraction.