paramvi's blog

Find all numbers between i,j which have 'D' as it's lowest common divisor(LCD).
By paramvi, 9 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?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is this problem from?

→ Reply
»
9 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
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why is it common divisor?

→ Reply
»
9 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
  • »
    »
    9 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
    • »
      »
      »
      9 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
  • »
    »
    9 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
  • »
    »
    9 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
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Surely, the first case is d > 100 :)

      → Reply
  • »
    »
    9 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
    • »
      »
      »
      9 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