最大公约数,Greatest Common Divisor(GCD),当然你要是叫它Highest Common Factor(HCF)也没人会说不行。
相信提到最大公约数大家都不会陌生,因为从小学开始我们就接触到了,
如果我们拿到的数是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)。
第一步:令
第二步:根据前提可知
第三步:根据第二步结果可知,
第四步:可以断定
不知道你有没有看懂。不过不重要我们来看代码吧。
联系客服