计算最大公因数的欧几里得算法

aqua0 2019-06-28

计算最大公因数的欧几里得算法

最大公因数
最大公因数,也称最大公约数,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b)。求最大公约数有多种方法,常见的有质因数分解法、辗转相除法等等。

欧几里得算法
欧几里德算法又称辗转相除法,是指用于计算两个正整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。欧几里得算法在RSA加密算法中有运用。

源码

//当N>M时,第一次循环之后两数将进行交换
int Gcd(int m,int n){
    int r;
    while(n > 0){
        r = m % n;
        m = n;
        n = r;
    }
    return m;
}

算法分析
算法通过连续计算余数,知道余数是0为止,最后所得的非0余数就是最大公因数。例如 M=1989 ,N=1590,则余数序列为399,393,6,3,0。因而,Gcd(1989,1590)=3,从余数的序列可知,这是一个快速收敛的算法。要想得出该算法的运行时间,就需要确定余数序列究竟有多长?不妨大胆的猜测log(N)看似是非常理想的答案,但是余数序列递减的规律并非是按照常数因子所递减的,事实上,数学家们已经证明了,在两次迭代以后,余数的值最多是原始值的一半。由此可知,迭代次数之多是2log(N) = O(logN)从而得到算法的时间复杂度。下面,我们从数学家那里问来了证明过程。

时间复杂度证明
定理:
如果 M > N ,则 M mod N < M/2
证明:如果 N<=M/2 ,则余数小于N,故定理在这种情况下成立
如果 N>M/2 ,此时M仅含有一个N,从而余数为M-N<M/2 ,定理成立。
从上面的例子来看,2logN 大约是20,但是实际上,我们只是运行了7次计算,可能有人会说,这个常数2不是最好的界限值。事实上,欧几里得算法的平均时间复杂度是需要大量的数学分析进行证明的,算法迭代的平均次数是(12ln2lnN)/pi^2+1.47。

有兴趣的同学可以研究一下质因数分解等其他算法哦

相关推荐