如何求兩數的最大公因數

求兩個數的最大公因數（Greatest Common Divisor, GCD）有幾種方法，其中最常用的是質因數分解法和歐幾里得算法（Euclidean algorithm）。

質因數分解法： 首先將兩個數分別分解為質因數的乘積，然後找出這些質因數中共同的因子，這些因子的乘積就是最大公因數。

例如，求54和36的最大公因數： 54 = 2 × 3 × 3 × 3 36 = 2 × 2 × 3 × 3 最大公因數是 2 × 3 × 3 = 18

歐幾里得算法（又稱輾轉相除法）： 這個算法是這樣工作的：用較小的數除以較大的數，得到一個餘數。然後用剛才除數（較大的數）除以這個餘數，又得到一個餘數。繼續這樣做，直到除數和被除數相同，此時的餘數就是它們的最大公因數。

例如，求12和18的最大公因數： 18 ÷ 12 = 1 R 6 12 ÷ 6 = 2 R 0 因為餘數為0，所以最大公因數是6。

在編程中，通常會使用一個循環來實現歐幾里得算法，直到兩個數相等或者其中一個數為0。以下是一個簡單的Python例子：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 使用例子
gcd(12, 18)  # 輸出: 6

這個算法時間複雜度為O(log(min(a, b)))，因為每次循環都會將較小的數減小一半。