文章目录
- 一、循环求解
- 二、辗转相除法
- 三、找最小 i 值
一、循环求解
- 首先两个数的最小公倍数一定大于两个数中较大的那个,且小于两数之积
- 找出a与b之间的较大值max
- 利用循环,令i=max,不断++,当i能同时整除a与b时,输出i,跳出循环
- 即i为最小公倍数
代码如下:
#include <stdio.h>
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("%d\n", i);
break;//跳出循环
}
}
return 0;
}
二、辗转相除法
-
以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数
-
两数乘积=最小公倍数*最大公约数
-
通过辗转相除法求出最大公约数即求得最小公倍数
-
图解举例:
代码如下:
#include<stdio.h>
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("%d\n", m/b);//乘积除以最大公因数等于最小公倍数
return 0;
}
三、找最小 i 值
- 一定会有一个整数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 值即可。
代码如下:
#include<stdio.h>
int main() {
int a, b;
scanf("%d %d", &a, &b);
int i = 1;//i从1开始找
while (a*i % b) {//(a*i)%b==0时为假,结束循环
i++;
}
printf("%d\n", a*i);
return 0;
}
更多推荐
【C语言初阶】求最小公倍数的三种方法
发布评论