Número de divisores comunes entre dos números dados

Question

¿Cómo puedo calcular el número de divisores comunes de dos naturales?

Por ejemplo, si consideramos (12,24) la respuesta es 6 es decir {1,12,2,6,3,4} .

EDIT : Tengo una respuesta aquí La solución se reduce a encontrar el número del divisor del GCD de los dos números.

Answer 1

El usuario2969 pidió la respuesta completa así que la publicaré aquí.

El primer paso es tomar el gcd de los dos números. Esto se puede hacer con el algoritmo euclidiano y es rápido: la implementación ingenua tarda un tiempo cuadrático, lo cual es bastante bueno. Llamemos a este número g.

El siguiente paso es factorizar g. Este es el paso más difícil si g es grande. Enfoque básico: dividir g por los primos hasta un límite fijo, digamos 10^5, o hasta que lo que quede sea menor que el cuadrado del primo actual. En este punto, compruebe la primalidad de lo que queda (primero con una prueba de Miller-Rabin y luego, si lo desea, con la prueba de su elección, APR-CL, ECPP, etc.). Si el número es compuesto, utilice el rho de Pollard y/o el SQUFOF de Shanks. (Siempre que encuentre un factor, compruebe su primalidad y la de su cofactor y vuelva a este paso si es compuesto). Si éstos no encuentran un factor, utilice ECM para buscar un factor pequeño. En un punto de cruce adecuado, puede utilizar MPQS/SIQS para factorizar el número. Si el número es mayor, aumente los límites de ECM. Si no se encuentra ningún factor hasta ~40 dígitos, considere la posibilidad de utilizar GNFS para factorizar lo que queda. Esto llevará al menos un día, dependiendo del tamaño del número restante.

Una vez que tienes la factorización es fácil contar el número de divisores: empieza un acumulador en 1, y para cada primo multiplica el acumulador por uno más que el exponente de ese primo.

Tenga en cuenta que para este problema puede ser capaz de cortocircuitar la factorización para los números de un tamaño adecuado por el ensayo de dividir hasta la raíz cúbica del número y demostrar que lo que queda es compuesto y no un cuadrado. En este caso, el número de divisores es el número de divisores de la parte factorizada por 4, ya que la parte no factorizada es un semiprimo libre de cuadrados.

---

Aquí hay algunos scripts para calcular el valor.

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

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

Answer 2

En respuesta al usuario2969 :

Primero hay que computar el gcd siempre es mejor utilizar Algoritmo euclidiano para esto, mi implementación en C++ para lo mismo:

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

Ahora tenemos que calcular el número de divisores de N = E_GCD(A,B) Esto se puede hacer de manera eficiente calculando primero la factorización utilizando cualquier algoritmo rápido como Factorización de enteros Pollard rho o ECM entonces usando la teoría de números estándar $\text{trick}^*$ para encontrar el número de factores, sin embargo en este problema si los valores de A y B son pequeños (digamos: $0 \lt A,B \le 10^6$ ), entonces no necesitamos realmente usar ninguno de esos sofisticados algoritmos, en su lugar podrías construir tu propio algoritmo simplemente basado en el hecho de que los factores de un número ocurren en par, es decir, si digamos i es un factor de N entonces también lo es $N/i$ usando esta observación clave construyo el algoritmo, aquí está mi implementación en C++ de esta 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);

Observe el hecho de que un número no puede tener un divisor que sea mayor que la raíz cuadrada del número, el resto del código creo que se explica por sí mismo.

* $\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$