Question

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

Answer 1

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

最大公因数

最大公因数，也称最大公约数，指两个或多个整数共有约数中最大的一个。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

从上面的例子来看，2logN 大约是20，但是实际上，我们只是运行了7次计算，可能有人会说，这个常数2不是最好的界限值。事实上，欧几里得算法的平均时间复杂度是需要大量的数学分析进行证明的，算法迭代的平均次数是（12ln2lnN）/pi^2+1.47。

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