The Magic Numbers

The Magic Numbers


Friends I am solving a problem but i am not able to understand how to start it. Any kind of help would be great. The problem statement is below.

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.
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.
For each test case, print a single line having the count of Magic Numbers in [L, R] .
1 ≤ T ≤ 10
2 ≤ N ≤ 50
1 ≤ L ≤ R ≤ 10^18


Hi Puspak64,

Where is this challenge from? Is this homework?

Here is the method I use to solve difficult algorithm challenges:

The wording of this challenge is pretty dense. The first thing I would do is try to rewrite the challenge in my own words to ascertain whether I really understood what it was asking me.

Usually problem sets like this have examples of input and expected output (for testing purposes). Do you have any examples of input/outputs? These can help you reword the challenge and check your understanding.

Once you have a clear sense of what the task is asking, consider a simple version of the algorithm that uses low numbers and try to come up with a process you can do with pen and paper, recording each step.

If you can come up with a manual pen and paper process that works with small numbers, try to automate that process. If the automated version gives you the same answer with small numbers, test a bigger set of numbers (preferably the ones you were given as an example).

I hope this helps :slight_smile:


It looks like it came from hackerearth. [L, R] probably means the set of all numbers from L to R, inclusive, so if you have [5, 10] that would mean the numbers 5, 6, 7, 8, 9, and 10. Same with [1, N].

So you’re looking for how many numbers between L and R are divisible by a prime number that doesn’t exceed N.