欧几里得算法（辗转相除法） 求两个正整数的最大公约数，时间复杂度 O(logn)。 欧几里得算法基于下面这个原理： 设a,b均为正整数，则gcd(a,b)=gcd(b,a%b)。  证明：设 a = kb + r，其中 k 和 r 分别为 a 除以 b 得到的商和余数。 则有 r = a - kb 成立。 设 d 为 a 和 b 的一个公约数， 那么由 r = a - kb，得 d 也是 r 的一个约数。 因此 d 是 b 和 r 的一个公约数。 又由 r = a % b，得 d 为 b 和 a % b 的一个公约数。 因此 d 既是 a 和 b 的公约数，也是 b 和 a % b的公约数。 ...