本文主要是介绍求最大公因数的经典算法：Euclid辗转相除法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求两整数最大公约数比较常用，我们可以自定义函数gcd使用：
int gcd(int a,int b)
{
int r;
while(b>0) //推荐使用，不必再讨论ab的输入大小情况
{ //时间复杂度为O(logN）
r=a%b;
a=b;
b=r;
}
return a;
}
或用三目运算符简化：
int gcd(int a,int b)
{ b>0?gcd(b,a%b）：a)}
如编写程序输入一个分数然后将其化为最简形式，就用到了gcd（先求分子分母最大公因数，然后同除它）
同样如果要求两个数的最小公倍数：为这两数乘积除以其最大公约数。
这篇关于求最大公因数的经典算法：Euclid辗转相除法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
