C语言第六十一弹—求最小公倍数

使用C语言求最小公倍数

定义:两个或多个整数公有的倍数叫做它们的公倍数,其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。

方法一:乘积/最大公因数法

已知 最小公倍数 = 整数乘积 / 最大公因数

思路:使用辗转相除法,获取最大公因数,然后使用整数乘积除以最大公因数即可.

#define _CRT_SECURE_NO_WARNINGS#include int main(){int a = 0, b = 0, c = 0;scanf("%d %d", &a, &b);int mul = a * b;while (c = a % b)//为0证明有最大公因数出现{a = b;b = c;}printf("%d ", mul / b);return 0;}

方法二:整除法(若k被整数同时整除,则k为公倍数,并且此时⼀定是最⼩公倍数)

思路:需要判断一个数是否能同时被则整除,需要一个一个数字进行测试,此时就需要使用循环,而最小公倍数必然是大于等于整数中最大的数,所以可以直接从最大数开始递增.当满足k被整数同时整除,证明是最小公倍数.

#define _CRT_SECURE_NO_WARNINGS#include int main() {int a = 0, b = 0, k= 0;scanf("%d %d", &a, &b);k= a > b ? a : b;//求最大整数while (1){if (k % a == 0 && k % b == 0)//寻找同时被整除的k{printf("%d ",k);//为真,打印break;}k++;//为假,继续递增即可}return 0;}