©2020-2024 ioDraw All rights reserved
最大公约数：指能够整除多个整数的最大正整数，而多个整数不能都为零。
最小公倍数：两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。
求最小公倍数的算法：
最小公倍数 = 两个整数的乘积 / 最大公因数
求最大公约数的算法：
第一种方法：辗转相除法
有两个整数a和b:
1. a % b ==temp;
2. 若temp = 0；那么b就是最大公约数。
3. 若temp ≠ 0；则a = b；b = temp；继续进行a % b 操作。
eg：求25和15的最大公约数，其过程为：
25 % 15 余 10 ； 15 % 10 余 5 ； 10 % 5 余 0 。因此5即为最大公约数
#include<stdio.h> int main() { int a , b , temp; printf("put in a and b : ");
scanf("%d %d",&a,&b); int nul = a * b; while (a * b != 0) { temp = a % b; a =
b; b = temp; } printf(" max = %d:",a); printf(" min = %d:", (nul / a) ); return
0; } put in a and b : 25 15 max = 5: min = 75:
第二种方法：相减法
取两个整数a、b：
1. 若a > b,则 a = a - b；
2. 若a < b,则 b = b - a；
3. 若 a = b,则 a(b)即为两数的最大公约数
4.若 a ≠ b,则继续执行第一步操作。
eg：求25和15的最大公约数，其过程为：
25 - 15 = 10(15 > 10);15 - 10 = 5(10 > 5);
10 - 5 = 5(5 == 5)
因此，25 和15的最大公约数为5。
代码如下：
#include<stdio.h> int main() { int a , b , m , n; printf("put in a and b:");
scanf("%d %d", &a, &b); m = a; n = b; while (a != b) { if(a > b) { a = a - b; }
else { b = b - a; } } printf("max = %d\n", a); printf("min = %d",(m * n)/a);
return 0; }
运行结果展示：
put in a and b:25 15 max = 5 min = 75
第三种方法：穷举法
有两个整数a和b：
1. 令 i = 1，
2. 如果 a，b能同时被i整除，则h = i；
3. i++；
4. 若 i <= a(b)，则继续执行第2步操作；
5. 若i > a(b)，当 i = a(b)时，穷举结束，则此时h即为最大公约数。
代码如下
#include<stdio.h> int main () { int a , b , m , n , i , h; printf("put in a
and b:"); scanf("%d %d", &a, &b); m = a; n = b; for( i = 1; i <= a; i ++) { if(
a % i == 0 && b % i == 0) { h = i; } } printf("max = %d\n", h); printf("min =
%d",(m * n) / h); return 0; }
运行结果展示：
put in a and b:25 15 max = 5 min = 75