Number of common divisors between two given numbers

Solution 1:

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

Solution 2:

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$