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

Etiquetas

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *