文章目录
最大公约数求法一：暴力求解求法二：更相减损法求法三：辗转相除法求法四：递归写法
最小公倍数求法一：暴力求解求法二：公式法
总结
最大公约数
什么是最大公约数呢？定义如下： 如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。 几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。
比如1：12、16的公约数有1、2、4，其中最大的一个是4，则4是12与16的最大公约数。 比如2：12、18的公约数有1、2、3、6，其中最大的一个是6，则6是12与18的最大公约数。 比如3：20、40的公约数有1、2、4、5、10、20，其中最大的一个是20，则20是20与40的最大公约数。
求法一：暴力求解
从上面举的例子我们可以分析，最大公约数一定不会大于两个数之间的最小数，最大也就是两个数的最小值，如20、40的最大公约数是20。
所以我们可以命令两个数的最小值为最大公约数，然后我们再用两个数分别除去这两个数的最小值，如果都能整除，则就是最大公约数，否则就自减1再用两个数分别除去，判断是否能整除，不能就自减1，一直循环下去直到找到都能被整除的数。（最坏的情况就是找到1停止）
比如上面的12、18这俩个数，这两个数的最小值是12，则定义变量tmp=12，然后判断12、18是否都能整除变量tmp。 tmp=12,不能被整除，自减1 tmp=11,不能被整除，自减1 tmp=10,不能被整除，自减1 tmp=9,不能被整除，自减1 tmp=8,不能被整除，自减1 ········ tmp=6,都能被12、18整除 所以找到最大公约数了，12，18的最大公约数是6。 思路分析完毕，代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include
int main()
{
int x = 0, y = 0;
printf("请输入两个数字：");
scanf("%d%d",&x,&y);
int tmp = x < y ? x : y; //把两个数的最小值赋给tmp
while (1)
{
if (x % tmp == 0 && y % tmp == 0)
{
break; //找到最大公约数了，跳出四循环
}
tmp--; //两个数都不能整除，自减1
}
printf("最大公约数是：%d", tmp);
return 0;
}
程序运行结果：
求法二：更相减损法
通过上面的求解我们可以了解，是非常的暴力。万一两个数是质数呢？那不是一直减到1才找到吗？有一点复杂。 所以我们要了解更相减损法，定义如下：
更相减损法：也叫更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。
思路分析： 以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到它们两个数相等为止。则相等的两个数就是所求的最大公约数。
代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include
int main()
{
int x = 0, y = 0;
printf("请输入两个数字：");
scanf("%d%d",&x,&y);
while (x != y) //两个数不相等就一直循环
{
if (x > y)
{
x = x - y;
}
else if (x < y)
{
y = y - x;
}
}
//到这里则是两个数相等，取其中的任何一个就是最大公约数
printf("最大公约数是：%d\n", x);
return 0;
}
程序运行结果：
求法三：辗转相除法
思路分析： 则相等的两个数就是所求的最大公约数。用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。 代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include
int main()
{
int x = 0, y = 0;
int tmp = 0;
printf("请输入两个数字：");
scanf("%d%d",&x,&y);
while ( y != 0)
{
tmp = x % y;
x = y;
y = tmp;
}
printf("最大公约数是：%d\n", x);
return 0;
}
求法四：递归写法
这个写法本质上也是更相减损法，只不够写法不同而已 代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include
int Fun(int x, int y)
{
if (x > y)
{
return Fun(y, x - y); //再开辟一个Fun函数
}
else if (x < y)
{
return Fun(x, y - x); //再开辟一个Fun函数
}
else //找到相减到相等
{
return x;
}
}
int main()
{
int x = 0, y = 0;
printf("请输入两个数字：");
scanf("%d%d",&x,&y);
int ret = Fun(x, y);
printf("最大公约数是：%d\n", ret);
return 0;
}
最小公倍数
什么是最小公倍数呢？定义如下： 几个数共有的倍数叫做这几个数的公倍数，其中除0以外最小的一个公倍数，叫做这几个数的最小公倍数。 举几个例子： 18、20的最小公倍数是180 12、18的最小公倍数是36 20、40的最小公倍数是40
求法一：暴力求解
通过上面举的例子我们可以发现 最小公倍数一定大于或等于两个数的最大值。
所以我们可以先找出两个数的最大值，然后赋值给变量tmp，然后用变量tmp分别除去两个数，如果能整除，则就是最小公倍数，否则变量tmp自加1，再分别除去两个数，判断是否能整除，一直循环下去，直到变量tmp都能够整除两个数。
比如12、18这两个数，这两个数的最大值是18，则定义变量tmp=18，然后判断变量tmp是否都能整除12、18。 tmp=18,不能整除12、18，自加1 tmp=19,不能整除12、18，自加1 tmp=20,不能整除12、18，自加1 tmp=21,不能整除12、18，自加1 tmp=22,不能整除12、18，自加1 ········ tmp=36,都能整除12、18 所以找到最小公倍数了，12，18的最小公倍数是36。
代码实现如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include
int main()
{
int x = 0, y = 0;
printf("请输入两个数字：");
scanf("%d%d",&x,&y);
int tmp = x > y ? x : y; //把两个数的最大值赋给tmp
while (1)
{
if (tmp % x == 0 && tmp % y == 0)
{
break; //tmp都能整除两个数，找到最小公倍数了，跳出死循环
}
tmp++; //不能整除，自加1
}
printf("最小公倍数是：%d\n",tmp);
return 0;
}
程序运行如下：
求法二：公式法
公式法定义如下： 由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。 所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用两个数的积除去最大公约数得出它们的最小公倍数。 因此我们可以利用上面任何一种求最大公约数的方法来实现，先求最大公约数然后再求最小公倍数。 代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include
int Fun(int x, int y)
{
if (x > y)
{
return Fun(y, x - y); //再开辟一个Fun函数
}
else if (x < y)
{
return Fun(x, y - x); //再开辟一个Fun函数
}
else //找到相减到相等
{
return x;
}
}
int main()
{
int x = 0, y = 0;
printf("请输入两个数字：");
scanf("%d%d", &x, &y);
int ret = Fun(x, y);
printf("最大公约数是：%d\n", ret);
printf("最小公倍数是：%d\n", x * y / ret); //利用公式法，直接求出
return 0;
}
程序运行结果：
总结
不管是求最大公约数还是最小公倍数，都用到了暴力求解法，是否发现很多相似的地方呢？ 求最大公约数是把最小值赋给变量tmp，然后两个数再除去变量tmp判断是否能整除，不能整除变量tmp就自减1，直到整除为止。
求最小公倍数是把最大值赋给变量tmp，然后变量tmp再分别除去两个数判断是否能整除，不能整除变量tmp就自加1，直到整除为止。 这就是我关于最大公约数和最小公倍数的看法了，大家还有什么要补充和指正的可以在评论区探讨哦。 都看到这里了，点个赞呗，感谢感谢。