Question

c语言最小公倍数的求法

Answer 1

c语言最小公倍数的求法如下：

两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。整数a，b的最小公倍数记为[a，b]，同样的，a，b，c的最小公倍数记为[a，b，c]，多个整数的最小公倍数也有同样的记号。

与最小公倍数相对应的概念是最大公约数，a，b的最大公约数记为（a，b）。关于最小公倍数与最大公约数，我们有这样的定理：(a,b)x[a,b]=ab(a,b均为整数)。

方法一：穷举法

假设有两个整数num1和num2，这两个整数的最小公倍数一定大于等于它们的最大值，同时小于等于它们的积。按从小到大的顺序遍历整个范围内的所有整数，第一个公因数即为它们的最小公倍数。【不考虑负数，求负数的最小公倍数本就是无意义的（相当于求两个正数的最大公倍数）】

方法二：定理法

使用定理求最小公倍数（两个整数的最小公倍数等于两数之积除以两个数的最大公因数），需要先求出两个整数的最大公因数，最大公因数这里采用辗转相除法。（最大公因数的求法可以参考我上一篇文章——第68天：求最大公约数（使用三种方法））【不考虑负数，求负数的最小公倍数本就是无意义的（相当于求两个正数的最大公倍数）】