/**
* 問題：求兩個數的最大公約數
* 解決方法：歐幾裡得的輾轉相除法
* @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
}
}
