求最大公约数
最大公约数的定义：如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。例： 在2、4、6中，2就是2，4，6的最大公约数。
知道了最大公约数的定义后，我们来学习一下最大公约数的求解方法。
1.暴力求解法
思路：假设有两个数m和n，先求出两个数中的较小值min，然后利用while循环找出m和n的最大公约数。while循环的循环体是如果m和n整除min同时为零，那么此时的min就是m和n的最大公约数；不符合该条件的话min自减一。
代码实现：
#include <stdio.h> int main() { int m, n; printf("请输入两个整数:>"); scanf("%d %d", &m, &n); int min = (m < n ? m : n); while (1) { if ((m % min == 0) && (n % min == 0)) { break; } min--; } printf("%d和%d的最大公约数是%d\n", m, n, min); return 0; }
输出结果：
2. 辗转相除法
辗转相除法， 又名欧几里德算法(Euclidean algorithm)，是求两个正整数之最大公约数的算法。它是已知最古老的算法， 其可追溯至公元前300年前。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
代码实现：
#include <stdio.h> int main() { int m, n; printf("请输入两个整数:>"); scanf("%d %d", &m, &n); int m1 = m; int n1 = n;//保存m和n的数据 int r = 0; while (r = m % n) { m = n; n = r; } printf("%d和%d的最大公约数是%d\n", m1, n1, n); return 0; }
输出结果：
求最小公倍数
最小公倍数的定义：如果一个数既是a又是b的倍数，那么我们就把这个数叫着a和b的公倍数，如果这个数在a b的所有公倍数里为最小，那这个数就是最小公倍数。例如，10和20的最小公倍数是20。
1.暴力求解法
假设有两个数m和n，先求出两个数中的最大值max，然后利用while循环找出m和n的最小公倍数。while循环的循环体是如果max整除m和n同时为零，那么此时的max就是m和n的最小公倍数；不符合该条件的话max自加一。
代码实现：
#include <stdio.h> int main() { int m, n; printf("请输入两个数:>"); scanf("%d %d", &m, &n); int max = (m > n ? m : n); while (1) { if ((max % m == 0) && (max % n == 0)) { break; } max++; } printf("%d和%d的最小公倍数是%d\n", m, n, max); return 0; }
输出结果：
2.最大公约数法
假设有两个数m和n，且m和n的最大公约数为x、最小公倍数y，那么最小公倍数和最大公约数存在一个关系式：m * n = x * y。例如这个关系式，我们就可以实现我们的代码了。
代码实现：
#include <stdio.h> int main() { int m, n; printf("请输入两个数:>"); scanf("%d %d", &m, &n); int m1 = m; int n1 = n; int r = 0; while (r = m % n) { m = n; n = r; } printf("%d和%d的最小公倍数是%d\n", m1, n1, m1 * n1 / n); }
输出结果：
3.奇技淫巧
因为最大公倍数肯定是其因素的整数倍，那么假设两个数为m和n，i等于1，其最小公倍数为k。如果m成i模除n为0，那么m*i就等于k，否则i++。
代码实现：
#include <stdio.h> int main() { int m, n; printf("请输入两个数:>"); scanf("%d %d", &m, &n); int i = 1; while (m*i%n!=0) { i++; } printf("%d和%d的最小公倍数是%d\n", m, n, m*i); return 0; }
输出结果：
本篇博客主要介绍了最大公约数和最小公倍数的几种常见方法。如果大家对其它的方法还感兴趣的话，可以自行查找，在这里就不在赘述了。最后，如果大家觉得有收获的话，大家可以点个赞支持一下！
结语
每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根。
