Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Below is what I need to calculate efficiently.

  1. Find the number of natural numbers which is divisor of both $N$ and $K$.
  2. Find the number of natural numbers which is divisor of $N$ and is divisible by $K$.
  3. Find the number of natural numbers which is divisor of N and is not divisible by K.

$$1\leq N\leq 10^{12} \\ 1\leq K \leq 10^{12}$$

$N$ would be constant for all the above queries whereas $K$ would change in the question. I know for first one I can calculate the GCD of $N$ and $K$ and then divide it by smaller of $N$ and $K$. But I have no clue about other 2 queries. please help me crack this.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

For 1, you need the number of factors of the GCD. You can't divide this GCD by either N or K (unless N=K).

For 2, you need the number of factors of $\frac NK$

For 3, take the number of factors of N, and subtract the result from 2.

share|improve this answer
    
@ross.. thanks a lot.. one question.. i think for n=10^12 no of divisors would be very less right.. 10^12 has 169 only.. so if i am doing it directly by computing all divisors , will be it a problem on exceution time.. –  Algorithmist Sep 5 '12 at 18:13
    
@Algorithmist: You'll need to factor it. You could see stackoverflow.com/questions/110344/… –  Ross Millikan Sep 5 '12 at 18:32
    
@Algorithmist: To factor numbers up to $10^{12}$ you only need primes up to $10^6$, which are quick to sieve (or read in from a data file). –  Ross Millikan Sep 6 '12 at 4:08
    
regarding the second query Find the number of natural numbers which is divisor of N and is divisible by K.Finding the divisors of N/K would not yield the correct result... for e.g suppose N=154 and k=24 then divisors of N/K=>6 would be 4 ..But actually there is no divisor of N which is divisible by K..Please suggest something. –  Algorithmist Sep 6 '12 at 6:11
    
@Algorithmist: the divide is not integer division, it is real division. $\frac {154}{24}$ is not an integer, so as you say there are none. $\frac{144}{24}=6$ and there are $4$ of them, $24, 48, 72, 144$ –  Ross Millikan Sep 6 '12 at 13:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.