Como calcular el máximo común divisor en Java

Hola a todos, hoy os voy a explicar como podemos calcular el máximo común divisor en Java.

En las matemáticas, se define el máximo común divisor (abreviado MCD) de dos o más números enteros al mayor número entero que los divide sin dejar residuo alguno (sin que sobre algún número).

En Java, el proceso que haremos el siguiente:

• Obtenemos en una variable a el número mayor de los dos números.
• Obtenemos en una variable b el número menor de los dos números.
• Creamos una variable resultado, donde guardaremos el valor de b.
• Hacemos el resto de a y b, guardándolo en la variable b y en la variable a se guarda el valor de resultado.
• Continuamos con el anterior paso hasta que el modulo de a y b sea 0.

Veamos cada paso en código:

Obtenemos en una variable a el número mayor de los dos números:

public static int mcd(int num1, int num2) {

    int a = Math.max(num1, num2);
    
}

Obtenemos en una variable b el número menor de los dos números.

public static int mcd(int num1, int num2) {

    int a = Math.max(num1, num2);
    int b = Math.min(num1, num2);
    
}

Creamos una variable resultado, donde guardaremos el valor de b:

public static int mcd(int num1, int num2) {

    int a = Math.max(num1, num2);
    int b = Math.min(num1, num2);

    int resultado = 0;
    
}

Hacemos el resto de a y b, guardándolo en la variable b y en la variable a se guarda el valor de resultado.

public static int mcd(int num1, int num2) {

    int a = Math.max(num1, num2);
    int b = Math.min(num1, num2);

    int resultado = 0;
    resultado = b;
    b = a % b;
    a = resultado;

    return resultado;
    
}

Continuamos con el anterior paso hasta que el modulo de a y b sea 0:

public static int mcd(int num1, int num2) {

    int a = Math.max(num1, num2);
    int b = Math.min(num1, num2);

    int resultado = 0;
    do {
        resultado = b;
        b = a % b;
        a = resultado;
    } while (b != 0);

    return resultado;
    
}

Veamos un ejemplo práctico:

public static void main(String[] args) {

    Scanner sn = new Scanner(System.in);

    System.out.println("Dame el primer numero");
    int num1 = sn.nextInt();

    System.out.println("Dame el segundo numero");
    int num2 = sn.nextInt();

    int res = mcd(num1, num2);
    
    System.out.println("MCD: " + res);
}

Este seria el resultado:

En ese caso, el MCD de 10 y 15 es 5, ya que tienen en común el 5 como divisor y es el máximo de ellos.

Os dejo el ejemplo completo:

import java.util.Scanner;

public class EjemploMCD{

    public static void main(String[] args) {

        Scanner sn = new Scanner(System.in);

        System.out.println("Dame el primer numero");
        int num1 = sn.nextInt();

        System.out.println("Dame el segundo numero");
        int num2 = sn.nextInt();

        int res = mcd(num1, num2);
        
        System.out.println("MCD: " + res);
    }

    public static int mcd(int num1, int num2) {

        int a = Math.max(num1, num2);
        int b = Math.min(num1, num2);

        int resultado = 0;
        do {
            resultado = b;
            b = a % b;
            a = resultado;
        } while (b != 0);

        return resultado;
        
    }

}

Os dejo un video donde lo explico paso a paso

Espero que os sea de ayuda. Si tenéis dudas, preguntad. Estamos para ayudarte