En este post te mostraré cómo calcular el máximo común divisor en Java, aplicando el algoritmo de Euclides. El máximo común divisor es aquel número entero mayor que divide a dos números sin dejar residuo.

Por ejemplo, el máximo común divisor de 50 y 120 es 10; pues no hay número mayor a 10 que divida a ambos números.

Te mostraré dos formas de obtener el MCD (Máximo común divisor) en Java. Uno usando el ciclo while y otro usando recursividad con funciones.

MCD con ciclo while

Para obtener este valor; dentro del ciclo while obtenemos el residuo de dividir a entre b y lo guardamos en b (pero guardando el valor de b en una variable temporal); en donde a es el primer número y b el segundo (de los que queremos obtener el máximo común divisor) hasta que b sea cero.

Finalmente regresamos el valor de a, que tendrá el último valor temporal antes de que b haya sido 0. En código, se traduce a lo siguiente:

See the gist on github.

En algún momento b será 0, y por lo tanto se detendrá el ciclo, regresando así el mcd.

Máximo común divisor en Java con recursión

Ahora apliquemos recursividad. De manera matemática, el MCD(a, b) es lo mismo que el MCD(a, a % b) en donde el signo % obtiene el residuo de la división.

Por lo tanto podemos diseñar una función recursiva que se detiene cuando b es 0, regresando el valor de a (pues cero no es válido).

See the gist on github.

Demostración

Y finalmente si quieres ver un uso de estos métodos, podemos probar con el código dentro de la función main.

Recuerda que en este caso he declarado las funciones estáticas porque estamos invocándolas sin crear una instancia de la clase, pero puedes adaptar el código a tus necesidades.

See the gist on github.

Al ejecutarlo, obtenemos:

Aquí puedes ejecutar el código; y en este enlace encuentras más contenido de Java.