最大公因數與最小公倍數

Intuitive Approach

計算最小公因數最直覺的方法，便是從 2 開始往上探索有哪個數字可以同時整除給定的兩數，探索到兩數中較小者為止，屆時若尚未找到（兩數護質），則 return 1，範例 Python 程式碼如下：

def gcd_intuitive(a: int, b: int) -> int:
    ans = 2
    m = min(a, b)
    
    while ans <= m:
        if a % ans == 0 and b % ans == 0:
            return ans
        ans += 1
    
    return 1

Time Complexity: $O(min(a, b))$

類似地，若要以最直覺的方式尋找最小公倍數，那就是從給定兩數中較大者開始往上探索有哪個數字可以同時被給定的兩數整除，範例 Python 程式碼如下：

def lcm_intuitive(a: int, b: int) -> int:
    ans = max(a, b)
    
    while True:
        if ans % a == 0 and ans % b == 0:
            return ans
        ans += 1

Time Complexity: $O(a \cdot b)$

---

有沒有更有效率的演算法呢？還記得小時候學過的「輾轉相除法」嗎：

Euclidean Approach

讓我們一樣從 gcd 開始：

def gcd_euclidean(a: int, b: int) -> int:
    if a == 0:
        return b
    return gcd_euclidean(b % a, a)

Time Complexity: $O(log(min(a, b)))$

接著輪到 lcm，我們一樣會用到一個小時後數學課教的概念：

$$a \cdot b = gcd(a, b) \cdot lcm(a, b)$$

也就是說，有了 gcd 的演算法後，要使用 euclidean approach 算出 lcm 簡直易如反掌：

def lcm_euclidean(a: int, b: int) -> int:
    return (a * b) // gcd_euclidean(a, b)

Time Complexity: $O(log(min(a, b)))$