1. Información general
En matemáticas, el MCD de dos enteros, que no son cero, es el entero positivo más grande que divide cada uno de los enteros de manera uniforme.
En este tutorial, veremos tres enfoques para encontrar el máximo divisor común (MCD) de dos números enteros. Además, veremos su implementación en Java.
2. Fuerza bruta
Para nuestro primer enfoque, iteramos desde 1 hasta el número más pequeño dado y verificamos si los números enteros dados son divisibles por el índice. El índice más grande que divide los números dados es el MCD de los números dados:
int gcdByBruteForce(int n1, int n2) { int gcd = 1; for (int i = 1; i <= n1 && i <= n2; i++) { if (n1 % i == 0 && n2 % i == 0) { gcd = i; } } return gcd; }Como podemos ver, la complejidad de la implementación anterior es O (min (n1, n2)) porque necesitamos iterar sobre el ciclo n veces (equivalente al número más pequeño) para encontrar el MCD.
3. Algoritmo de Euclides
En segundo lugar, podemos usar el algoritmo de Euclid para encontrar el GCD. El algoritmo de Euclid no solo es eficiente, sino también fácil de entender y de implementar usando la recursividad en Java.
El método de Euclides depende de dos teoremas importantes:
- Primero, si restamos el número más pequeño del número más grande, el MCD no cambia; por lo tanto, si seguimos restando el número, finalmente terminamos con su MCD.
- En segundo lugar, cuando el número más pequeño divide exactamente al número más grande, el número más pequeño es el MCD de los dos números dados.
Tenga en cuenta en nuestra implementación que usaremos módulo en lugar de resta, ya que básicamente son muchas sustracciones a la vez:
int gcdByEuclidsAlgorithm(int n1, int n2) { if (n2 == 0) { return n1; } return gcdByEuclidsAlgorithm(n2, n1 % n2); }Además, observe cómo usamos n2 en la posición de n1 y usamos el resto en la posición de n2 en el paso recursivo del algoritmo .
Además, la complejidad del algoritmo de Euclides es O (Log min (n1, n2)), que es mejor en comparación con el método de fuerza bruta que vimos antes.
4. Algoritmo de Stein o algoritmo GCD binario
Finalmente, podemos usar el algoritmo de Stein, también conocido como algoritmo Binary GCD , para encontrar el GCD de dos enteros no negativos. Este algoritmo utiliza operaciones aritméticas simples como cambios aritméticos, comparación y resta.
El algoritmo de Stein aplica repetidamente las siguientes identidades básicas relacionadas con GCD para encontrar GCD de dos números enteros no negativos:
- mcd (0, 0) = 0, mcd (n1, 0) = n1, mcd (0, n2) = n2
- Cuando n1 y n2 son números enteros pares, entonces mcd (n1, n2) = 2 * mcd (n1 / 2, n2 / 2) , ya que 2 es el divisor común
- Si n1 es un número entero par y n2 es un número entero impar, entonces mcd (n1, n2) = mcd (n1 / 2, n2) , ya que 2 no es el divisor común y viceversa
- Si n1 y n2 son números enteros impares, y n1> = n2 , entonces mcd (n1, n2) = mcd ((n1-n2) / 2, n2) y viceversa
Repetimos los pasos 2-4 hasta que n1 sea igual a n2 , o n1 = 0 . El MCD es (2n) * n2 . Aquí, n es el número de veces que 2 se encuentra en común en n1 y n2 mientras se realiza el paso 2:
int gcdBySteinsAlgorithm(int n1, int n2) { if (n1 == 0) { return n2; } if (n2 == 0) { return n1; } int n; for (n = 0; ((n1 | n2) & 1) == 0; n++) { n1 >>= 1; n2 >>= 1; } while ((n1 & 1) == 0) { n1 >>= 1; } do { while ((n2 & 1) == 0) { n2 >>= 1; } if (n1 > n2) { int temp = n1; n1 = n2; n2 = temp; } n2 = (n2 - n1); } while (n2 != 0); return n1 << n; }Podemos ver que usamos operaciones aritméticas de desplazamiento para dividir o multiplicar por 2. Además, usamos la resta para reducir los números dados.
La complejidad del algoritmo de Stein cuando n1> n2 es O ((log 2 n1) 2) mientras que. cuando n1 <n2, es O ((log 2 n2) 2).
5. Conclusión
En este tutorial, analizamos varios métodos para calcular el MCD de dos números. También los implementamos en Java y echamos un vistazo rápido a su complejidad.
Como siempre, el código fuente completo de nuestros ejemplos aquí está, como siempre, en GitHub.