求最大公约数问题

最大公约数问题，也不是个很难的问题，如果知道思路就很容易了。对于最大公约数问题，最简单的思路应该算是直接循环从1开始用两个数对其做除法了，找出最大公约数。不过这思路太没技术含量了，效率也低，如果数字很大，还是很慢的。

一般解决最大公约数问题的方法是：辗转相除法（欧几里德算法）。

算法思想为（注意：b<a）：

1.a÷b，令r为所得余数（0≤r＜b）。若r=0，算法结束；b即为答案。

2.互换：置a←b，b←r，并返回第一步。

根据这个思路，可以使用循环搞定，当然，很明显可以用递归搞定。

还有一种思路解决最大公约数问题，称为更相减损术，思路也很简洁，大概如下：对于a、b，如果a>b,那么a=a-b，否则b=b-a；循环以上操作，直到a=b，那么a=b=最大公约数。

以下是上述算法的程序代码：

view plain

#include <stdio.h>         /*  更相减损法  */   int gcd1(int a,int b)   {       while(a!=b)       {           if(a>b)               a=a-b;           else                b=b-a;       }       return a;   }      /*  辗转相除法  求两个数的最大公约数  */   int gcd2(int a,int b)   {       if(a<b)       {           a=a+b;           b=a-b;           a=a-b;       }          int r;       while(b!=0)       {           r=a%b;           a=b;           b=r;           }       return a;   }      /*  辗转相除法  递归解法  */   int gcd3(int a,int b)   {       if(b==0)           return a;       else return gcd3(b,a%b);   }      int main()   {       printf("最大公约数：%d/n",gcd1(9,3));       printf("最大公约数：%d/n",gcd2(9,3));       printf("最大公约数：%d/n",gcd3(9,3));       return 0;   }

对于求最小公倍数的问题，如果求出了最大公约数，那么就很容易了，因为：

最小公倍数=a*b/gcd(a,b)。为了防止a*b溢出，可以写成：a/gcd(a,b)*b。