求最大公约数问题

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

1. #include <stdio.h>  
2.   
3.   
4. /* 
5. 更相减损法 
6. */  
7. int gcd1(int a,int b)  
8. {  
9.     while(a!=b)  
10.     {  
11.         if(a>b)  
12.             a=a-b;  
13.         else   
14.             b=b-a;  
15.     }  
16.     return a;  
17. }  
18.   
19. /* 
20. 辗转相除法 
21. 求两个数的最大公约数 
22. */  
23. int gcd2(int a,int b)  
24. {  
25.     if(a<b)  
26.     {  
27.         a=a+b;  
28.         b=a-b;  
29.         a=a-b;  
30.     }  
31.   
32.     int r;  
33.     while(b!=0)  
34.     {  
35.         r=a%b;  
36.         a=b;  
37.         b=r;      
38.     }  
39.     return a;  
40. }  
41.   
42. /* 
43. 辗转相除法 
44. 递归解法 
45. */  
46. int gcd3(int a,int b)  
47. {  
48.     if(b==0)  
49.         return a;  
50.     else return gcd3(b,a%b);  
51. }  
52.   
53. int main()  
54. {  
55.     printf("最大公约数：%d/n",gcd1(9,3));  
56.     printf("最大公约数：%d/n",gcd2(9,3));  
57.     printf("最大公约数：%d/n",gcd3(9,3));  
58.     return 0;  
59. }  

 

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

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