數論-歐幾裡得算法(輾轉相除法)

1. 設  a = kb + r, 其中 a, b, q, r 都為整數, 那麼:
           gcd(a, b) = gcd(b, r)
              

2. 設整數 a, b 且 b != 0. 做帶餘除法 a = qb + r, (0 <= r <= |b|). 
   若 r = 0, gcd(a, b) = b;
   若 r > 0, 在對b 于 r做帶除餘法 b = q'r + r'.
   若 r' = 0, gcd(a, b) = gcd(b, r) = r;
   重複上述過程, 直到餘數為0;
              

3. 最大公約數  =  gcd(a, b);
   最小公倍數 = lcm(a, b) = (a * b)/gcd(a, b)
              

4. 代碼實作:

int gcd(int a, int b)
    {
        return b == 0 ? a : gcd(b, a%b);
    }

    int lcm(int a, int b)
    {
        return (a * b)/gcd(a, b);
    }