E12.【C语言】练习：求两个数的最大公约数

1.枚举 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{int a = 0;int b = 0;int tmp = 0;scanf("%d %d", &a, &b);if (a < b){for (int i=1; i < a; i++){if (0==a% i  && 0==b%i)tmp = i;}}if (a>b){for (int i = 1; i < b; i++){if (0 == b % i && 0 == a % i)tmp = i;}}if (a = b)tmp = a;printf("%d", tmp);return 0;
}

注意i不能从0开始否则有Integer division by zero报错，即整数除以零

但是代码可以进一步简化：

输入两个数-->找出最小数-->从最小数开始：从大向小找，一旦找到就是最大公约数

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{int a = 0;int b = 0;int tmp = 0;scanf("%d %d", &a, &b);if (a > b)tmp = b;elsetmp =a;while (1)//一直循环{if (0 == a % tmp && 0 == b % tmp){printf("%d", tmp);break;}tmp--;}return 0;
}

2.辗转相除法 

定义：先用较大的数除以较小的数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。此时的除数就是所求的最大公约数。

18%24=18-->24%18=6-->18%6=0-->6是最大公约数

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{int a = 0;int b = 0;int tmp = 0;scanf("%d %d", &a, &b);while (tmp=a%b)//循环,m%n=0退出{a = b;b = tmp;}printf("%d", b);return 0;
}

最小公倍数=a*b/最大公约数