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

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

两个数字的LCM(最小公倍数)是可以被两个数字除以的最小的数字。

例如,15和20的LCM是60,而5和7的LCM是35。

查找两个数字的LCM的C程序

一个简单的解决方案是找到两个数字的所有质因数,然后找到两个数字中的所有因子的并集。最后,返回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))

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C语言 实例