欧几里得算法实现、正确性证明及时间复杂度分析

求最大公约数的最常用的算法是欧几里得算法，也称为辗转相除法。
问题定义为求i和j的最大公约数gcd(i, j)，其中i和j是整数，不妨设i>j。
算法可以递归的表示:

1. 如果j能整除i，那么gcd(i,j)=j；
2. j不能整除i，令r=i%j，那么gcd(i, j)=gcd(j, r)。
   使用C语言实现:

   int gcd(int i, int j)
   {
       int r = i % j;
       return r == 0 ? j : gcd(j, r);
   }

正确性分析：
算法的步骤1，显然成立（最大公约数定义）。关键是要证明步骤2。
设d是i和j的最大公约数，
那么i=md，j=nd，m和n互质(否则d不是最大公约数)。
由r=i%j可以得到i=kj+r, k=⌊m/n⌋, k≥1(我们前面假设过i>j)。
把i=md，j=nd代入得到
md=knd+r
那么
r=(m-kn)d
m-kn和n也是互质的
所以得到d是j和r的最大公约数。

时间复杂度分析：
逆着看该算法，最后的余数是0，倒数第二次余数是d，倒数第三次是kd，k>1…
由于组成了一个数列，{0,d,kd,nkd+d,…}
数列的n项加上n+1项，比n+2项要小，所以比斐波纳契数列增长的要快。
我们已知斐波纳契数列增长速度是指数，那么待分析的数列也是指数增长。
设欧几里得算法需要k次，那么j=O(2^k)，则k=O(lg j)。
所以欧几里得算法求最大公约数的时间复杂度是对数量级的，速度非常快。