- 一、循环求解
- 二、辗转相除法
- 三、找最小 i 值
一、循环求解
- 首先两个数的最小公倍数一定大于两个数中较大的那个,且小于两数之积
- 找出a与b之间的较大值max
- 利用循环,令i=max,不断++,当i能同时整除a与b时,输出i,跳出循环
- 即i为最小公倍数
代码如下:
#include二、辗转相除法int main() { int a, b; scanf("%d %d", &a, &b); int max = a > b ? a : b; //找出较大值 int i = 0; for (i = max; i <= a*b; i++) { if (i%a == 0 && i%b == 0) { printf("%dn", i); break;//跳出循环 } } return 0; }
-
以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数
-
两数乘积=最小公倍数*最大公约数
-
通过辗转相除法求出最大公约数即求得最小公倍数
-
图解举例:
代码如下:
#include三、找最小 i 值int main() { int a, b; scanf("%d %d", &a, &b); int m = a * b; int r = 0; while (r = a % b) {//r为0时,跳出循环,此时b为最大公因数 a = b; b = r; } printf("%dn", m/b);//乘积除以最大公因数等于最小公倍数 return 0; }
- 一定会有一个整数k能够使k/a=i,k/b=j;
- a * i为整数表示k为a的倍数,k%b为0表示k为b的倍数,即(a * i)%b==0,此时a和b的公倍数为k,即a * i;
- 要求最小公倍数即找出符合要求的最小的 i 值即可。
代码如下:
#includeint main() { int a, b; scanf("%d %d", &a, &b); int i = 1;//i从1开始找 while (a*i % b) {//(a*i)%b==0时为假,结束循环 i++; } printf("%dn", a*i); return 0; }