对于求解这两道道例题有很多种不同的解法，比如辗转相除法，穷举法，等等，这次简单介绍一下。
求最大公约数
1.辗转相除法
辗转相除法， 又名欧几里德算法（Euclidean algorithm。 它的具体做法是：用较小数除较大数，再用出现的余数（第一个余数）去除除数，再用出现的余数（第二个余数）去除第一个余数，如此反复，直到最后余数是0为止。
代码如下：
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int eual(int a, int b) { int t; while (b != 0) { t = a % b; a = b; b = t; } return a; } int main() { int a, b; scanf("%d%d", &a, &b); printf("eual=%d\n", eual(a, b)); return 0; }
2.穷举法
由于a和b的最大公约数不可能比a和b中的较小者还大，否则一定不能整除它，因此，先找到a和b中的较小者min，然后从min开始逐次减1尝试每种可能，即检验min到1之间的所有整数，第一个满足公约条件的min，就是a和b的最大公约数。
代码如下
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int main() { int a, b, min; scanf("%d %d", &a, &b); min = a < b ? a : b; while (!(a % min == 0 && b % min == 0)) { min--; } printf("%d", min); return 0; }
求最小公倍数
1.穷举法
m和n的最小公倍数一定比m和n大，也就是说要>= m，n的较大值
找到这个最大值，并且不断的++，总能找到一个值能够同时整除m和n
代码如下
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int main() { int m, n, k; scanf("%d %d", &m, &n); k = m > n ? m : n; for (k;; k++) { if (k % m == 0 && k % n == 0) break; } printf("%d", k); return 0; }
2.改良版的穷举法
代码如下：
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int main() { int m, n; scanf("%d %d", &m, &n); int i=1; while(m*i % n !=0) { i++ } printf("%d", m*i); return 0; }
