前言 对于初学编程的小伙伴们肯定经常遇见此类问题，而且为之头疼，今天我来给大家分享一下，最大公因数和最小公倍数的求法。
让我们开始吧！
文章目录 1，最大公因数 法1 法2 法3 2，最小公倍数 3，尾声 1，最大公因数 首先提起最大公因数大家最先想到的就是辗转相除法。
假如求a，b的最大公因数x。
其中a>b。
a可以表示为n b+t,那么t=a-n b,因为x是a和b的公因数，将等式两边同时除以x得，t/x=a/x-n*b/x,那么我肯可以知道t/x是个整数，所以x是a和a%b的公因数，那么我们可知那么x也是b和a%b的公因数。
所以a和b的最大公约数和b和a%b的最大公约数是一样的。
那么我们就可以使用循环的方法求出最大公因数如下： 法1
#include
int gcd(int a, int b)
{
if (a > b)//判断大小事大数除以小数
{
int temp = a;
a = b;
b = temp;
}
while (a % b)//辗转相除
{
int temp = a;
a = b;
b = temp%b;
}
return a;
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
int ans = gcd(a,b);
printf("%d", ans);
return 0;
}
那么这样写有点麻烦，我们可以直接使用递归的方法解决而且速度更快。
法2
#include
int gcd(int a, int b)
{
if (a == 0)//当a为0时，b为最大公因数
return b;
return gcd(b, a%b);
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
if(a>b)
int tem = a;
a = b ;
b = tem;
int ans = gcd(a,b);
printf("%d", ans);
return 0;
}
那么有没有更快的方法呢？
当然有！
我们都知道位运算的速度比除法运算快的多，那么我肯可以吧代码改成这样。
切记，a要大于b才能使用。
法3
#include
int gcd(int a, int b)
{
while (b ^= a ^= b ^= a %= b);//连等式是从右往左计算的，我们要知道a^a=0,a^0=a。
那么连等式就可以等同于gcd（b,a%b）
return a;
}
int main()
{
int a, b;
scanf("%d %d", &a, &b);
int ans = gcd(a,b);
printf("%d", ans);
return 0;
}
这种算法是最快的 2，最小公倍数 正常求法求最小公倍数可能太过麻烦，但是我们要知道一个定理。
假设x是a和b的最大公因数，y是a和b的最小公倍数，那么x * y=a * b。
（如果不明白可以百度一下或者直接背下来当结论用） 所以我们就可以用上面的方法先求出x然后再用y=a * b/x求出y的值。
3，尾声 本期的分享到这里结束，如果觉得博主讲的不错的话请给博主一个点赞一个收藏支持一下，我们下期再见！