最大公因數程式

最大公因數（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("Enter the first number: "))
b = int(input("Enter the second number: "))
gcd_value = gcd(a, b)
print("The GCD of", a, "and", b, "is", gcd_value)

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

歐幾里得算法的原理是：對於整數a和b，其中a >= b，gcd(a, b)等於gcd(b, a % b)，其中a % b表示a除以b的餘數。這個算法通過不斷地將較小的數字代換為餘數，直到餘數為0為止，最後返回的數字就是a和b的GCD。