最大因數計算機

最大公因數（Greatest Common Divisor, GCD）也稱為最大公約數，是指兩個或更多整數共有最大的正因子。在數學中，通常使用質因數分解來計算最大公因數。

例如，要找出數字24和36的最大公因數，我們可以將它們分解成質因數：

24 = 2 × 2 × 2 × 3 36 = 2 × 2 × 3 × 3

從這裡可以看出，24和36都包含因子2 × 2 × 3，所以它們的最大公因數是12。

在計算機科學中，有幾種算法可以用來計算最大公因數，其中最著名的是埃拉托斯特尼篩法（Eratosthenes' sieve）和更高效的歐幾里得算法（Euclidean algorithm）。

歐幾里得算法是這樣工作的：假設我們要找出數字a和b的最大公因數，我們可以先找出a除以b的餘數c（記為a % b = c），然後用b和c來代替a和b，重複這個過程，直到b為0。此時，a就是我們要找的最大公因數。

以下是一個簡單的Python程式碼範例，使用歐幾里得算法來計算最大公因數：

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

# 使用例子
print(gcd(24, 36))  # 輸出應該是12

這個程式碼使用了Python的除法運算符%來得到餘數，然後在每次循環中，將較小的數字賦值給較大的數字，直到最小的數字為0。最後，返回較大的數字作為最大公因數。