您当前的位置:首页 > 计算机 > 编程开发 > C语言

C语言求最小公倍数的三种方法

时间:07-29来源:作者:点击数:

第一种方法:累加法求

思路是,两个数字,要求他们的最小公倍数,那么这个最小公倍数,至少不要比这两个要求的数小。我们首先判断出两个数中较大的一个,然后判断这个数是否是要求的两个数的最小公倍数。如果不是,这个数加一,继续判断,循环往复,直到找出最小公倍数。该方法属于遍历的方法,效率较低。

代码:

int main()

{

int a = 0;

int b = 0;

printf("输入求的数:");

scanf("%d%d", &a, &b);

int max = a > b ? a : b;//求出两数中较大的一个

while (max % a != 0 || max % b != 0)//判断是否能整除两个要求的数,不能则+1

{

max++;

}

printf("最小公倍数为:%d", max);

return 0;

}

第二种方法:

思路:首先明确一点,最小公倍数一定是a和b的倍数,那么我们锁定a或b中的一个,这边以a举例,a的n倍如果能够整除b,那么这个数一定是a和b的公倍数,我们从1倍开始加起,找到最先可以整除的数,就是a和b的最小公倍数。较第一种更快速。

代码:

int main()

{

int a = 0;

int b = 0;

printf("输入数:");

scanf("%d%d", &a, &b);

int i = 1;//倍数,从1倍开始

while (a * i % b != 0)//如果a的i倍可以整除b,则a的i倍为a和b的最小公倍数

{

i++;

}

printf("%d", a * i);

return 0;

}

第三种方法:利用最大公约数求最小公倍数

思路:a和b的乘积,是a和b的最小公倍数和最大公约数的乘积,我们先利用辗转相除法求得a和b的最大公约数,再用a和b的乘积除去最大公约数即可求得最小公倍数。

辗转相除法求最大公约数:以除数余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数

代码:

int main()

{

int a = 0;

int b = 0;

printf("输入数:");

scanf("%d%d", &a, &b);

int c = a * b;

int ptr = 0;

while (a % b != 0)//辗转相除法求最大公约数

{

ptr = b;

b = a % b;

a = ptr;

}

printf("%d", c / b);

return 0;

}

如果这篇文章对你有帮助,还请点赞支持一下,谢谢

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门