求最大公因數程式

最大公因數（Greatest Common Divisor, GCD），也稱為最大公約數，是指兩個或更多整數共有因數中的最大一個。在數學中，通常使用歐幾里得算法（Euclidean algorithm）來計算兩個整數的GCD。

以下是一個簡單的Python程式，使用歐幾里得算法來計算兩個整數的GCD：

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

# 使用例子
a = int(input("請輸入第一個整數："))
b = int(input("請輸入第二個整數："))
gcd_value = gcd(a, b)
print("最大公因數為：", gcd_value)

這個程式定義了一個名為gcd的函數，它接收兩個整數a和b作為參數，並使用歐幾里得算法來計算它們的GCD。在主程式中，用戶被要求輸入兩個整數，然後呼叫gcd函數來計算它們的GCD，並將結果列印出來。

歐幾里得算法的原理是：對於整數a和b，其中a >= b，gcd(a, b)等於gcd(b, a % b)，其中a % b表示a除以b的餘數。這個算法通過不斷將較大的數字減去適當倍數的較小數字，直到兩個數字相等為止，這時得到的數字就是a和b的最大公因數。