求最大公因数的经典算法：Euclid辗转相除法

本文主要是介绍求最大公因数的经典算法：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辗转相除法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---