paramvi's blog

Find all numbers between i,j which have 'D' as it's lowest common divisor(LCD).
By paramvi, 10 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is this problem from?

→ Reply
»
10 years ago, # |
  Vote: I like it -29 Vote: I do not like it

what do you mean "lowest common divisor" ? you dont know any single thing about maths.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why is it common divisor?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      In a sieve you have

      `for(int i=2;i<=sqrt(limit);i++)

      {

      if(!a[j])

 for(int j=i*i;j<=limit;j++)a[j]=i;//Instead of just marking a[i]

      }`

      This will find the smallest prime divisor for every element from 2 to limit.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Seems correct. Edit:For d>100 n/d<=2e7. Also if d is not prime then the asnwer is 0.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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??

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Surely, the first case is d > 100 :)

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I don't understand how we can do that because my solution will depend on number of primes less than D.

      → Reply