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.

How can I compute the number of common divisors of two naturals ?

For example,if we consider (12,24) the answer is 6 i.e {1,12,2,6,3,4}.

EDIT : I got an answer here.The solution boils down to finding the number of divisor of the GCD of the two numbers.

share|improve this question
    
So what do you want now? –  anonymous Nov 2 '10 at 5:59
    
I edited the question to remove ambiguity. Since d|a,b iff d|gcd(a,b) it reduces to finding the number of divisors of the gcd, which has an obvious closed form in terms of the exponents of its prime divisors - as in your link. –  Bill Dubuque Nov 2 '10 at 16:10
    
@ Bill Dubuque : Thanks. –  Quixotic Nov 2 '10 at 18:26

2 Answers 2

up vote 6 down vote accepted

user2969 asked for the full answer so I'll post it here.

The first step is to take the gcd of the two numbers. This can be done with the Euclidean algorithm and is fast: the naive implementation takes quadratic time, which is good enough. Call this number g.

The next step is to factor g. This is the hardest step if g is large. Basic approach: divide g by the primes up to some fixed limit, say 10^5, or until what remains is less than the square of the current prime. At this point test what remains for primality (first with a Miller-Rabin test then, if desired, with the test of your choice, APR-CL, ECPP, etc.). If the number is composite, use Pollard's rho and/or Shanks' SQUFOF. (Whenever you find a factor, check it and its cofactor for primality and return to this step if composite.) If those fail to find a factor, use ECM to search for a small factor. At an appropriate crossover point you may wish to use MPQS/SIQS to factor the number instead. If the number is larger, increase the bounds on ECM. If no factor is found to ~40 digits, consider using GNFS to factor what remains. This will take at least a day, depending on the size of the remaining number.

Once you have the factorization it's easy to count the number of divisors: start an accumulator at 1, and for each prime multiply the accumulator by one more than the exponent of that prime.

Note that for this problem you may be able to short-circuit the factorization for numbers of an appropriate size by trial-dividing up to the cube root of the number and showing that what remains is composite and not a square. In this case the number of divisors is the number of divisors of the factored part times 4, since the unfactored part is a squarefree semiprime.


Here are some scripts to calculate the value.

Pari/GP: common(m,n) = numdiv(gcd(m,n))

Mathematica: Common[m_,n_] := DivisorSigma[0,GCD[m,n]]

share|improve this answer
    
This is a nice description! It's clear enough that one could probably write working code from this (assuming appropriate subroutines are already in place). Thanks. –  J. M. Nov 4 '10 at 14:46

In response to user2969 :

At first you need to computed the gcd, it is always best to use Euclidean algorithm for this,my C++ implementation for the same :

int E_GCD(int a,int b){
   return b ? gcd(b,a%b):a;
}

Now we need to compute the number of divisors of N = E_GCD(A,B), this can be done efficiently by first computing the factorization using any fast algorithm like Pollard rho integer factorization or ECM then using the standard number theory $\text{trick}^*$ to for finding the number of factors,however in this problem if the values of A and B are small (say:$0 \lt A,B \le 10^6$),then we don't need really need to use any of such sophisticated algorithms,instead you could build up your own algorithm simply based on the fact the the factors of a number occur in pair that is if say i is a factor of N then so is $N/i$ using this key observation I build up the algorithm,here is my C++ implementation of this idea :

  N = E_GCD(A,B);
  int ans = 0;
  int sqt = (int)sqrt(N);
  for(int i = 1 ; i <= sqt; i++){
      if(N % i == 0){
          ans += 2 ;
          if(i == N/i) ans--;
      }
  }
  printf("%d\n",ans);

Notice the fact that a number cannot a have a divisor which is greater than the square root of the number,rest of the code I believe is self explanatory.

*$\text{If }N = a^p \cdot b^q \cdot c^r \cdots \text{,a,b,c ... are primes,number of factors of N is :}(p+1) \cdot (q+1)\cdot(r+1)\cdots$

share|improve this answer

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.