Programa Java para encontrar MCD y MCM de dos números usando el algoritmo de Euclides

MCD o el Máximo Común Divisor de dos números dados A y B es el número más alto que divide completamente a A y B, es decir, deja el resto 0 en cada caso. MCM o el Mínimo Común Múltiplo de dos números dados A y B es el Mínimo número que se puede dividir tanto por A como por B, dejando el resto 0 en cada caso.

El MCM de dos números se puede calcular en el enfoque de Euclides usando el MCD de A y B.

MCM(A, B) = (a * b) / MCD(A, B)

Ejemplos:

Entrada: A = 20, B = 30

Salida:
MCD = 10
LCM = 60

Explicación:
El número más alto que divide a 20 y 30 es 10. Entonces, el MCD de 20, 30 es 10.
El número más bajo que se puede dividir entre 20 y 30, dejando el resto 0 es 60.
Entonces, el MCM de 20 y 30 es 60 .

Entrada: A= 33, B= 40

Salida:
GCD = 1
LCM = 1320

Algoritmo de Euclides para calcular GCD:

Este método para calcular el MCD se basa en el principio de que el MCD de dos números A y B sigue siendo el mismo incluso si el número mayor se reemplaza por el módulo de A y B. En este método, realizamos la operación mcd en A y B repetidamente reemplazando A con B y B con el módulo de A y B hasta que el módulo se convierte en 0.

A continuación se muestra la implementación de para encontrar MCD y MCM de dos números usando el algoritmo de Euclides:

// Java program to compute
// GCD of two numbers
// using Euclid's algorithm
  
import java.io.*;
  
class GFG {
  
    // gcd method returns the GCD of a and b
    static int gcd(int a, int b) {
        
        // if b=0, a is the GCD
        if (b == 0)
            return a;
        
        // call the gcd() method recursively by
        // replacing a with b and b with
        // modulus(a,b) as long as b != 0
        else
            return gcd(b, a % b);
    }
  
    // lcm() method returns the LCM of a and b
    static int lcm(int a, int b, int gcdValue)
    {
        return Math.abs(a * b) / gcdValue;
    }
  
    // Driver method
    public static void main(String[] args) {
  
        int a = 20, b = 30, gcdValue;
        gcdValue = gcd(a, b);
        
        // calling gcd() over
        System.out.println("GCD = " + gcdValue);
        
        // calling lcm() over integers 30 and 20
        System.out.println("LCM = " + lcm(a, b, gcdValue));
    }
}

GCD = 10
LCM = 60