求最大公约数问题

最大公约数问题，也不是个很难的问题，如果知道思路就很容易了。对于最大公约数问题，最简单的思路应该算是直接循环从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=最大公约数。

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

#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。