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

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

输出:

LCM of 15 and 20 is 60

时间复杂度: O(log(min(a,b))

辅助空间: O(log(min(a,b))

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例