最大公因數（Greatest Common Divisor - GCD）

最大公因數（Greatest Common Divisor，GCD；或Highest Common Factor，簡寫為HCF），指某幾個整數共有因數中最大的一個。

求兩個整數最大公因數主要的方法：

• 列舉法：各自列出因數，再找出最大的公因數。
• 質因數分解法：兩數各作質因數分解，然後取出共有的項乘起來。
• 短除法
• 輾轉相除法（Euclid's algorithm）：常使用於直觀上不容易判別公因數的場合。

輾轉相除法（Euclid's algorithm）的思維為：

gcd(a, b) = gcd(b, a % b) 以下為其實作：

func gcd(a: Int, _ b: Int) -> Int {
    let r = a % b
    if r != 0 {
        return gcd(b, r)
    } else {
        return b
    }
}


gcd(52, 39)        // 13
gcd(228, 36)       // 12
gcd(51357, 3819)   // 57

以下為第三例的分解動作：

gcd(51357, 3819)

依輾轉相除法的規則，下式左右是等價的：

gcd(3819, 51357 % 3819) = gcd(3819, 1710)

之後的步驟為：

gcd(3819, 1710) = gcd(1710, 3819 % 1710) =

gcd(1710, 399) = gcd(399, 1710 % 399) =

gcd(399, 114) = gcd(114, 399 % 114) =

gcd(114, 57) = gcd(57, 114 % 57) =

gcd(57, 0)

當出現餘數為0時，就是兩樹的最大公因數，以此例即為57：

gcd(3819, 51357) = gcd(57, 0) = 57

每個步驟數字會越來越小，並且出現其中一個數字變為0。也會有兩數知最大公因數為1的情況，如下例：

gcd(841, 299) // 1

以下為以迴圈的方式實作輾轉相除法的程式碼：

func gcd(m: Int, _ n: Int) -> Int {
    var a = 0
    var b = max(m, n)
    var r = min(m, n)

    while r != 0 {
        a = b
        b = r
        r = a % b
    }
    return b
}

實作中max()與min()用以使迴圈中的除法確保是較大數除以較小數的情況。這在遞迴法中不需要，原因為較小數除以較大數的餘數為原數，會在遞迴過程中成為下一輪的除數。

最小公倍數（Least Common Multiple）

最小公倍數是數論中的一個概念。若有一個數X，可以被另外兩個數A、B整除，且X大於（或等於）A和B，則X為A和B的公倍數。A和B的公倍數可以有很多個，而所有的公倍數中，最小的公倍數就叫做最小公倍數。兩個整數公有的倍數稱為它們的公倍數，其中最小的一個正整數稱為它們兩個的最小公倍數。

例子： lcm(2, 3) = 6

要計算最小公倍數，以可以用輾轉相除法，其關係為：

lcm(a, b) = a * b / gcd(a, b)

實作如下：

func lcm(m: Int, _ n: Int) -> Int {
    return m*n / gcd(m, n)
}

lcm(10, 8)    // 40