C++程序查找两个数字的最小公倍数

两个数的最小公倍数是可以同时被两个数整除的最小的数字。

例如，15和20的最小公倍数为60，5和7的最小公倍数为35。

C++程序查找两个数字的最小公倍数

一个简单的解决方法是找到两个数字的所有质因子，然后找到存在于两个数字的因子中的所有因子的联合。最后，返回并集中元素的乘积。

基于以下两个数字’a’和’b’的最小公倍数的公式，可以实现一个高效的解决方案。

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

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

我们已经讨论了查找两个数字GCD的函数。使用GCD，我们可以找到LCM。

以下是上述思想的实现：

// 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; 
}