Milly and the Magic Numbers Milly likes to solve problems very much. Today she is solving a problem in which she has N, L and R and she has to find out the total count of Magic Numbers in [L, R] . Magic Numbers are the numbers which are divisible by at least one prime number in [1, N] . Being a beginner in programming, this one seems too hard for her to solve. So, she is asking you for her help, so your task is to solve this problem. Input First line of the input will have a integer T(number of test cases). Then each of the next T lines will contain 3 space separated integers: N, L and R. Output For each test case, print a single line having the count of Magic Numbers in [L, R]. Constraints 1 ≤ T ≤ 10 2 ≤ N ≤ 50 1 ≤ L ≤ R ≤ 10^{18} Sample Input 2 5 1 10 10 10 20 Sample Ouput 8 7 asked 05 Dec '16, 15:11

@arpit728 It can be easily solved, if you know that the number of multiples of any number(say x) occurs upto certain number(say n) is equal to the $floor(n/x)$ (example: number of multiples of 4 upto 42 is $floor(42/4)=10$). In this question we can calculate number of multiples (between L and R) of each prime number less than N one by one. But this will include some numbers multiple time (example: for n=6, L=1 and R=32, 30 will be counted three times as multiple of 2, 3 and 5.), so we need to subtract that multiples of numbers formed by multiplying prime numbers two at a time. In above example, those numbers will be $2*3=6$, $2*5=10$ and $3*5=15$, but this will remove 30 three times so we need to add the count of multiples formed by multiplying primes taken three at a time (i.e., $2*3*5=30$). total count = $\sum$(count of multiples of primes taken one at a time)  $\sum$(count of multiples of product of prime taken two at a time) + .... $\sum$(count of multiples of product of all prime numbers) Example: N=6,L=1 and R=31; Let, count(x) = number of multiples of prime number x; answered 05 Dec '16, 15:54
Please explain the subtraction logic in more details. How the elements that are being counted multiple times is taken care of.
(05 Dec '16, 22:34)
@arpit728 I've added an example to clear the logic.
(06 Dec '16, 00:44)
@arpit728 If you feel your question has been answered, mark it as accepted.
(06 Dec '16, 00:46)

You can apply a sieve solution... Complexity: O(nlog(n)) for marking the multiples and O(n) for counting... answered 05 Dec '16, 17:54

Where do you get the 31/2 uhh, mate? answered 06 Dec '16, 10:46
@banghasan I've taken the value of R as 31 in the example.
(06 Dec '16, 10:55)
