We need to find all numbers between i,j which have 'D' as it's lowest common divisor(LCD). By LCD 'D' of n, I mean there don't exist any number 1<d<D, which divides n.
Constraints : 1<=i<=j<=2*10^9; 1<=D<=2*10^9;
If the constraints hadn't been that much large, it can be trivially solved using sieve of Eratosthenes.
Solution to this problem is appreciated.
Example : lets i,j,D have values 4,16,5 respectively.
So the answer will be following set of numbers: 5. Here 10,15 are not in the answer because 10 is divisible by 5 as well as 2, which is less than 5. Same for 15. Hope it clarify the doubts.
Where is this problem from?
It was asked in a company's qualifying round on hackerrank.
Did you do it ?
no i did not
to clarify: has it ended?
what do you mean "lowest common divisor" ? you dont know any single thing about maths.
why is it common divisor?
LCD(n, n)?
The name still a bit confuses me but if I understand statement correctly I have idea how to calculate the number of such numbers(You just can't print them all fast if d = 2)
I will solve the problem for i=1, j=n.(Excercise: how to solve it with i > 1?)
We need to find all number that are less or equal to n/d and don't have divisors strictly less than d. Suppose d>100, then n/d<=2e7 and you can just use sieve to find smallest divisor for every number in O(n/d)
If d < 100 then there are at most 25 primes less than n and you could use inclusive-exclusive principle to calc those number.
Thanks I get it but can you explain how can we calculate the smallest divisor for every number in O(n/d). I mean how to find the smallest divisor of a number in O(1).
In a sieve you have
`for(int i=2;i<=sqrt(limit);i++)
{
}`
This will find the smallest prime divisor for every element from 2 to limit.
Seems correct. Edit:For d>100 n/d<=2e7. Also if d is not prime then the asnwer is 0.
If d<100 then how is n/d <= 2e7?. I think it should be n/d >= 2e7. And how do you handle the case when d>100??
Surely, the first case is d > 100 :)
riadwaw Can't we solve it using inclusion-exclusion principle for any D? Since D<=2*10^9,D can't have more than 11 prime factors.So by inclusion-exclusion principle,we could find [ (Numbers in the range divisible by D) — ( Numbers in the range divisible by any of the prime factors of D) ].Since 2^11 is very less,we could easily apply the inclusion-exclusion principle to all the subsets of D's prime factors.
Well, I don't understand how we can do that because my solution will depend on number of primes less than D.