本文主要是介绍三 求最大公约数（公因数）和最小公倍数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
写在前面
求最大公约数和最小公倍数其实是很基础的东西，在刚入门时就会学
这里我想补充一些我从别人那里学到的方法（当然也非常简单，大牛可以不用往下看了）
先看求最大公约数
一 求最大公约数
先看一个无脑的最简单的
简单枚举
思路很简单，我们都知道，n,m（n>m）最大公约数的最大值为m，也就是两数中较小的数，最小值为1
所以我们循环枚举区间（1，m]的数，判断能不能被n和m同时整除
然后我们来看代码
int gcd(int a,int b) {int g=a>b?b:a; //判断a，b的大小，若a大则取b while(g>1 && (a%g!=0||b%g!=0)) //枚举 g--;return g;
}
但是枚举太麻烦，如果数据很大的话时间就会爆
所以我们还有一种数学方法
辗转相除法
辗转相除法又叫欧几里得算法，具体思路如下
用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数 （来自百度百科 因为我是个语文渣渣表达不清）
那么我们用循环就可解决
代码如下
int gcd(int a,int b) {int t;while(t=a%b) { //辗转相除 a=b; //一次求余以后更新一次数值 b=t;}return b;
}
当然，辗转相除也可以用递归做
由思路我们可以得出，递归关系式为gcd(n,m)=gcd(m,n%m); 递归终止条件为gcd(m,0)=m;
所以我们有了以下代码 极致压行你值得拥有
long long gcd(long long n,long long m){return (m==0)?n:gcd(m,n%m); //递归
}
时间复杂度不知道
因为我也不太会算
但是又一个问题来了，如果数据要求高精度怎么办？
我们还有一种算法
二进制算法
二进制算法就不用取模运算了，只涉及减法和除以2的运算，更快，也更适合高精度运算
思路看下面
1.若a、b都是偶数，则gcd(a,b)=2*gcd(a/2,b/2)
2.若a是奇数、b是偶数，则gcd(a,b)=gcd(a/2,b/2)
3.若a、b都是奇数，则gcd(a,b)=gcd((a-b)/2,b)
因为我也是从别人那里学的，所以放上出处
参考链接点这里
代码我就不写了，上面的链接里有
（其实是懒得写）
于是求最大公约数的我就草率认真地讲完了
接下来我们看下一节，求最小公倍数
二 求最小公倍数
（其实这个我也不太会）
我最常用的方法是
利用数学技巧
好吧，说了跟没说一样
大家应该都知道，假设m，n的最大公约数是x，最小公倍数是y，那么有
m * n=x * y
于是我们利用上面的求最大公约数的方法快速算出最大公约数x
再用两数的乘积除以x就可以得到最小公倍数y了
代码也十分简单
long long gcd(long long n,long long m){return (m==0)?n:gcd(m,n%m);
}
int main(){long long n,m;cin>>n>>m;cout<<(n*m)/gcd(n,m);return 0;
}
是不是很容易！
可能有人会问，如果你不知道这个公式怎么办？
你看了这篇文章就知道了啊
那么你可以看这里
然后就没有然后了
简单收尾
END
这篇关于三 求最大公约数（公因数）和最小公倍数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
