Programa C++ para encontrar el MCM de dos números

MCM (Mínimo común múltiplo) de dos números es el número más pequeño que se puede dividir entre ambos números.

Por ejemplo, MCM de 15 y 20 es 60 y MCM de 5 y 7 es 35.

Una solución simple es encontrar todos los factores primos de ambos números y luego encontrar la unión de todos los factores presentes en ambos números. Finalmente, devuelva el producto de elementos en unión.

Una solución eficiente se basa en la siguiente fórmula para MCM de dos números ‘a’ y ‘b’.

   a x b = LCM(a, b) * GCD (a, b)

   LCM(a, b) = (a x b) / GCD(a, b)

Hemos discutido la función para encontrar el MCD de dos números . Usando GCD, podemos encontrar LCM. 

A continuación se muestra la implementación de la idea anterior:

// C++ program to find LCM
// of two numbers
#include <iostream>
using namespace std;
 
// Recursive function to return
// gcd of a and b
long long gcd(long long int a,
              long long int b)
{
  if (b == 0)
    return a;
  return gcd(b, a % b);
}
 
// Function to return LCM of
// two numbers
long long lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}
  
// Driver code
int main()
{
    int a = 15, b = 20;
    cout << "LCM of " << a <<
            " and " << b <<
            " is " << lcm(a, b);
    return 0;
}

LCM of 15 and 20 is 60

Complejidad del tiempo: O(log(min(a,b))

Espacio auxiliar: O(log(min(a,b))

¡ Consulte el artículo completo sobre Programa para encontrar MCM de dos números para obtener más detalles!