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.