最大公因數題目

最大公因數（Greatest Common Divisor, GCD），又稱為最大公約數，是指兩個或更多個整數中最大的那個共同因子。例如，對於整數24和36，它們的共同因子有1, 2, 3, 4, 6, 12, 24。其中，24是它們的最大公因數。

最大公因數可以用質因數分解的方法來求解。例如，求解18和24的最大公因數：

18 = 2 × 3 × 3 24 = 2 × 2 × 2 × 3

從質因數分解的結果可以看出，18和24都包含因數2和3。在18中，有兩個3，而在24中，有兩個2。因此，我們可以通過從18和24中分別減去多餘的因數來逐步消除共同的因子，直到剩下來的數字不再有共同的因子為止。

18 - 3 = 15 (因為18已經包含了兩個3，所以我們減去一個3) 15 - 3 = 12 (因為15還有一個3，所以再減去一個3) 12 = 2 × 2 × 3 (這時12和24已經沒有共同的因子了)

所以，18和24的最大公因數是12。

在計算機科學中，通常使用更高效的算法來求解最大公因數，例如Euclidean算法（歐幾里得算法）。這個算法的基本思想是，兩個數字的GCD等於它們中較小的數與兩數相除的餘數的GCD。以下是一個使用Euclidean算法求解最大公因數的例子：

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

# 示例
gcd(18, 24)  # 返回12

這個算法的時間複雜度為O(log(max(a, b)))，其中a和b是需要求解最大公因數的兩個數。