本文主要向大家介绍了C++语言程序设计的用辗转相除法求最大公约数，通过具体的代码向大家展示，希望对大家学习C++语言有所帮助。

C++代码如下

[cpp] view plain copy
1. #include "main.h"  
2. #include <iostream>  
3. using namespace std;  
4. int main()  
5. {  
6.     int a, b; int a_cup, b_cup, res;  
7.     cout << "Enter two integer:" << endl;   
8.     cin >> a ;  
9.     cin >> b ;  
10.     if (a > 0 && b >0)   
11.     {   
12.         a_cup = a;   
13.         b_cup = b;   
14.         while (b_cup)   
15.         {   
16.             res = a_cup % b_cup;   
17.             a_cup = b_cup;   
18.             b_cup = res;   
19.         }  
20.         cout << "Greatest common divisor:" << a_cup << endl;   
21.         cout << "Lease common multiple :"  <<  a * b / a_cup << endl;   
22.     }   
23.     else printf("Error!\n");   
24.   
25.     getchar();  
26.   
27.     return 0;  
28. }</iostream>

辗转相除法的实现，是基于下面的性质：

　　1：(a,b)=(a,ka+b)，其中a、b、k都为自然数
　　就是说，两个数的最大公约数，将其中一个数加到另一个数上，得到的新数组，其公约数不变，比如(4,6)=(4+6,6)=(4,6+2×4)=2。这里有一个比较简单的证明方法来说明这个性质：如果p是a和ka+b的公约数，p整除a，也能整除ka+b。那么就必定要整除b，所以p又是a和b的公约数，从而证明他们的最大公约数也是相等的。

　　还有另外一个性质也是很必要：
　　2：(0,a)=a
　　由这两个性质得到的，就是更相减损术：
　　(78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2
　　基本上思路就是大数减去小数，一直减到能算出来为止。不过在平时的计算过程中，往往不必计算到最后一步，比如在上面的过程中，到了(8,6)，就已经能够看出其结果。
　　我们可以看到，在上面的过程中，由(78,14)到(8,14)完全可以一步到位，因为(78,14)=(14×5+8,14)=(8,14)，由此就诞生出我们的辗转相除法。
　　用辗转相除法求(a,b).设r0=b，r1=a，反复运用除法算式，得到一系列整数qi，ri和下面的方程：


　　r0=q1r1+r2，r2＜r1(r2,r1)
　　r1=q2r2+r3，r3＜r2(r3,r2)
　　r2=q3r3+r4，r4＜r3(r4,r3)
　　………………
　　rn-3=qn-2rn-2+rn-1，rn-1＜rn-2 (rn-1,rn-2)
　　rn-2=qn-1rn-1+rn，rn-2＜rn-1 (rn-1,rn)
　　rn-1=qnrn。 (rn,0)
　　相当于每一步都运用原理①把数字进行缩小，上面右边就是每一步对应的缩小结果，可以看出，最后的余数rn就是a和b的公约数。我们以一个题为例说明基本过程。

　　例题：求(326,78)

　　326=4×78+14(78,14)

　　78=5×14+8 (14,8)

　　14=1×8+6 (6,8)

　　8=1×6+2 (6,2)

　　6=3×2 (0,2)

　　所以(326,78)=2。这和我们用更相减损术算出来的结果是一样的。

    本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！