C程序 查找两个数字的最小公倍数
两个数字的LCM(最小公倍数)是可以被两个数字除以的最小的数字。
例如,15和20的LCM是60,而5和7的LCM是35。
一个简单的解决方案是找到两个数字的所有质因数,然后找到两个数字中的所有因子的并集。最后,返回union中元素的乘积。
一个有效的解决方案是基于以下两个数字’a’和’b’的LCM公式。
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 <stdio.h>
// Recursive function to return
// gcd of a and b
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to return LCM of
// two numbers
int lcm(int a, int b)
{
return (a / gcd(a, b)) * b;
}
// Driver code
int main()
{
int a = 15, b = 20;
printf("LCM of %d and %d is %d ",
a, b, lcm(a, b));
return 0;
}
输出:
LCM of 15 and 20 is 60
时间复杂度: O(log(min(a,b))
辅助空间: O(log(min(a,b))