最大公约数（GCD）

最大公约数，Greatest Common Divisor(GCD)，当然你要是叫它Highest Common Factor(HCF)也没人会说不行。

最大公约数

相信提到最大公约数大家都不会陌生，因为从小学开始我们就接触到了，

短除法对吧！大概是这样的：

最大公因数 = 2*3 = 6

如果我们拿到的数是103287和417145，我们还可以通过短除法轻松的解决吗？

所以要给大家介绍两种新的求法，第一种的思维过程很简单，穷举法，思路就是枚举每一个数，如果两个数字都可以整除就说明这个是公因数，最大公因数当然要从大往小举了！从两个数的较小值到1。有一个符合就可以听停止了。

我们看到就算要求的a和b很大也可以轻松求解。

很明显，这个算法的事件复杂度是O(min(a,b))，线性的时间复杂度。接下来要介绍的辗转相除法效率就更高了。

转转相除法

欧几里得算法

用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。

关于它的证明......感兴趣的人看一下吧

设两数为a、b(a>b)，用gcd(a,b)表示a，b的最大公因数，r=a (mod b) 为a除以b的余数，k为a除以b的商，即a/b = k······r。辗转相除法即是要证明

gcd(a,b)=gcd(b,r)。

第一步：令，则设

第二步：根据前提可知

第三步：根据第二步结果可知，也是的因数

第四步：可以断定与互质（这里用反正法进行证明：设，则，则，则a与b的一个公约数，故c非a与b的最大公约数，与前面结论矛盾，因此c也是b与r的最大公约数）从而可知继而。

不知道你有没有看懂。不过不重要我们来看代码吧。

.