How to approach this kind of number theory based problems?

general
, , , ,
1

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 ≤ 1018

Sample Input

2

5 1 10

10 10 20

Sample Ouput

8

7

1 Like
2

@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).

So, it can be generalized as:

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;

So, total = (count(2) + count(3) + count(5)) - ((count(2*3) + count(3*5) + count(2*5)) + ((count(2*3*5));
Final answer will be number of multiples till R - number of multiples till L, but in this example as L is 1 so we don’t need to calculate seperately for L.

count(2) = floor(31/2) = 15 (2,4,6,8,10,12,14,16,18,20,22,24,26,28,30)

count(3) = floor(31/3) = 10 (3,6,9,12,15,18,21,24,27,30)

count(5) = floor(31/5) = 6 (5,10,15,20,25,30)

count(2*3) = floor(31/6) = 5 (6,12,18,24,30)

count(3*5) = floor(31/15) = 2 (15,30)

count(2*5) = floor(31/10) = 3 (10,20,30)

count(2*3*5) = floor(31/30) = 1 (30)

total = (15+10+6) - (5+2+3) + (1) = 22

1 Like
3

You can apply a sieve solution…

  1. iterate from 2 to n

    &nbsp 1. now mark all its multiples

    &nbsp 2. add this marked element into a set

  2. In the set now find all the marked elements between l and r

Complexity:- O(nlog(n)) for marking the multiples and O(n) for counting…

4

@srd091

Please explain the subtraction logic in more details. How the elements that are being counted multiple times is taken care of.

5

@arpit728 I’ve added an example to clear the logic.

6

@arpit728 If you feel your question has been answered, mark it as accepted.

7

Hey guys, check my website: http://codingeek.org/

8

Where do you get the 31/2 uhh, mate?

9

@banghasan I’ve taken the value of R as 31 in the example.