GCD算法求最大公因數與最小公倍數

1.更相減損法

gcd(a, b) = gcd(b, a-b); //終止條件：a==b -> return a;           

2.輾轉相除法

gcd (a, b) = gcd(b, a%b); //終止條件：!(a%b) -> return b;           

3.歐幾裡得算法

// 非遞歸算法
// 縮減更相減損法的時間複雜度的同時，避免了輾轉相除法的餘數溢出問題
int gcd(a, b) {
    int p2 = 1;
  	// 求得a與b共有的、最大的、數值為2^n的因子，并把n儲存至p2
    while(!(a&1 || b&1)) {	
        a >>= 1;
        b >>= 1;
        p2 ++;
    }
  	// 求得後，使a與b均除盡2，因為這時至少有一個數已不能被2整除
    while (!a&1) a >>= 1;
    while (!b&1) b >>= 1;
  	// 調整使得總滿足a>=b
    if (a<b) {int t = b; b = a; a = t;}
  	// 同時使用“gcd(a,b) = gcd(b,a%b)”與由上代碼確定的“至少有一個數不能被2整除”兩條性質，完成循環
  	// 退出條件為更疊相減再除二确定的值為奇數（使用最大公約數的數學性質）
    while (!((a=(a-b)>>1) & 1)) {
        while (!a&1) a >>= 1;
        if (a<b) {int t = b; b = a; a = t;}	// 反複交換
    }
    return b << p2;	// 乘回b的2^n，求得真正的最大公約數
}