C++程序 查找两个数字的最小公倍数
两个数的最小公倍数是可以同时被两个数整除的最小的数字。
例如,15和20的最小公倍数为60,5和7的最小公倍数为35。
一个简单的解决方法是找到两个数字的所有质因子,然后找到存在于两个数字的因子中的所有因子的联合。最后,返回并集中元素的乘积。
基于以下两个数字’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))