计算最大公约数（最大公因数）方法

可能大家有点忘记以前的数学知识，现在回忆一下。

1.约数（即因数）、倍数

约数（又称因数）：整数a除以整数b（b！=0）除得的商正好是整数而没有余数，b称为a的约数，a称为b的倍数。

2.公约数（即公因数）

公因数：如果一个数c既是数a的因数又是数b的因数，那么c叫做a和b的公因数

3.最大公约数（即最大公因数）

最大公因数：两个数的公因数中最大的一个，叫做这两个数的最大公因数

4.计算最大公约数的方法

a.枚举法

枚举法：将两个数的因数分别--列出，从中找出其公因数，再从公因数中找出最大的一个，即为这两个数的最大公因数。

b.短除法（即分解质因数的算法叫短除法）

(短除法同样适用于求最小公倍数，只需将其所有除数与最后所得的商相乘即可)

短除法：短除号就像一个倒过来的除号，先写要求最大公因数的两个数a,b，k从2开始，如果两个数a,b同除K，除尽则k+1,否则，最大公因数就是这些k的乘积。

，该式最大公约数：2*3=6.

b.分解因式法

将需要求最大公因数的两个数a,b分别分解质因数，再从中找出a,b公有的质因数，把这些共有的质因数相乘即得a,b的最大公约数。

c.欧几里得算法（辗转相除法）

欧几里得算法：对要求最大公因数的两个数a,b，设b<a，先用b除a，得a=b*q+r1（0<=r1<b）。若r1=0，则（a,b）=b；若r1!=0，则再用r1除b，得b=r1*q+r2（0<=r2<r1）,若r2=0，则（a,b）=r1，若r2!=0，则继续用r2除r1....如此循环，直到能整除为止，其最后一个非零余数即为（a,b）。

设两数为a、b(b<a），用gcd(a,b）表示a，b的最大公约数，r=a mod b 为a除以b以后的余数，辗转相除法即是要证明gcd(a,b)=gcd(b,r）。令c=gcd(a,b），则设a=mc，b=nc，根据前提有r =a-kb=mc-knc=(m-kn)c

由上，可知c也是r的因数，故可以断定m-kn与n互素【否则，可设m-kn=xd，n=yd，（d>1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公因数成为cd，而非c】

所以 gcd(b,r)=c，继而gcd(a,b)=gcd(b,r）。

例：求8251和6105的最大公因数。

考虑用较大数除以较小数，求得商和余数：

8251=6105×1+2146

6105=2146×2+1813

2146=1813×1+333

1813=333×5+148

333=148×2+37

148=37×4

最后除数37是148和37的最大公因数，也就是8251与6105的最大公因数

欧几里得算法计算公式：gcd（a,b）=gcd（b,a%b）

d.更相减损术

更相减损术出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

第一步：任意给定两个正整数a、b；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。这个数就是a、b的最大公约数。

例：求98与63的最大公因数。

分析：由于63不是偶数，把98和63以大数减小数，并辗转相减：

98-63=35

63-35=28

35-28=7

28-7=21

21-7=14

14-7=7

所以，98和63的最大公约数为7。

更相减损术计算公式：gcd（a,b）=gcd（b,a-b）

5.总结

1. 以上首三个方法（枚举法，短除法，分解因式法）同样适用于求多个自然数的最大公约数

2. 更相减损术和欧几里得算法的主要区别在于前者所使用的运算是“减”，后者是“除”。

从算法思想上看，两者并没有本质上的区别，

但是在计算过程中，如果遇到一个数很大，另一个数比较小的情况，可能要进行很多次减法才能达到一次除法的效果，从而使得算法的时间复杂度退化为O(N)，其中N是原先的两个数中较大的一个。相比之下，辗转相除法的时间复杂度稳定于O(logN)。

3. 总的来说欧几里得算法比较稳定