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:

public static int maximoComunDivisor(int a, int b) {
    int temporal;//Para no perder b
    while (b != 0) {
        temporal = b;
        b = a % b;
        a = temporal;
    }
    return a;
}

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).

public static int maximoComunDivisorRecursivo(int a, int b) {
    if (b == 0) return a;
    return maximoComunDivisorRecursivo(b, a % b);
}

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.

public class Main {

    public static void main(String[] args) {
        int a = 50;
        int b = 120;
        int mcd = maximoComunDivisor(a, b);
        System.out.printf("El MCD de %d y %d es %d\n", a, b, mcd);
        int mcdRecursivo = maximoComunDivisorRecursivo(a, b);
        System.out.printf("El MCD de %d y %d (con recursividad) es %d\n", a, b, mcdRecursivo);
    }

    public static int maximoComunDivisor(int a, int b) {
        int temporal;//Para no perder b
        while (b != 0) {
            temporal = b;
            b = a % b;
            a = temporal;
        }
        return a;
    }

    public static int maximoComunDivisorRecursivo(int a, int b) {
        if (b == 0) return a;
        return maximoComunDivisorRecursivo(b, a % b);
    }
}

Al ejecutarlo, obtenemos:

En este enlace encuentras más contenido de Java.