求最大公因數

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

要找到兩個整數的最大公因數，可以使用質因數分解法、歐幾里得算法（Euclidean algorithm）或者輾轉相除法等方法。對於較小的數字，質因數分解法可能更直觀，例如：

對於整數24和36，它們的質因數分解分別為： 24 = 2^3 3^1 36 = 2^2 3^2

可以看到，24和36都包含因子2^2和3^1，因此它們的最大公因數是2^2 * 3^1 = 12。

對於較大的數字，歐幾里得算法或輾轉相除法可能是更有效的方法。例如，可以使用以下Python代碼來計算兩個數字的最大公因數：

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

# 示例
gcd(24, 36)  # 輸出: 12

這個算法的原理是，每次將較小的數字（b）賦值給較大的數字（a），然後將a除以b的餘數賦值給b。這樣做直到b為0，此時a就是兩個數字的最大公因數。