/**
* 问题：求两个数的最大公约数
* 解决方法：欧几里得的辗转相除法
* @author xiaoxiaolan
*
*/
public class Gcd {
public static void main(String[] args) {
int m = 686996996, n = 53435566;
System.out.println("求解" + m + "和" + n + "的最大公约数。");
System.out.println("欧几里得的辗转相除算法实现:");
System.out.println(divisor(m, n));
System.out.println("Stein算法实现:");
System.out.println(gcd(m, n));
}
/**
* 这个是使用java中的递归方法实现辗转相除法
* 传统算法与证明： 定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)
* 证明：a可以表示成a = kb+ r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a,d|b，而r = a - kb，因此d|r 因此d也是（b,a mod b）
* 的公约数 因此（a,b）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，得证
* @param m
* @param n
* @return
*/
private static int divisor(int m, int n) {
if (m % n == 0) {
return n;
} else {
return divisor(n, m % n);
}
}
/**
* 和欧几里德算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。
* 为了说明Stein算法的正确性，首先必须注意到以下结论： gcd(a,a) = a，也就是一个数和他自身的公约数是其自身 gcd(ka,kb) =
* k gcd(a,b），也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除
* @param a
* @param b
* @return
*/
private static int gcd(int a, int b) {
if (a < b) // arrange so that a>b
{
int temp = a;
a = b;
b = temp;
}
if (0 == b) // the base case
return a;
if (a % 2 == 0 && b % 2 == 0) // a and b are even
return 2 * gcd(a / 2, b / 2);
if (a % 2 == 0) // only a is even
return gcd(a / 2, b);
if (b % 2 == 0)// only b is even
return gcd(a, b / 2);
return gcd((a - b) / 2, b);// a and b are odd
}
}
