最大公約數算法

最大公約數（Greatest Common Divisor, GCD）也稱為最大公因數，是指兩個或更多整數的共有最大因子。例如，對於整數24和18，它們的GCD是6，因為6是它們的共有最大因子。

在計算機科學中，有很多算法可以用來計算兩個整數的GCD，其中最著名的是埃拉托斯特尼質數篩（Eratosthenes' sieve）和更高效的更相剋除法（Euclidean algorithm）。

更相剋除法是這樣工作的：

1. 假設我們有兩個數字a和b，我們要找出它們的GCD。
2. 使用a除以b得到一個餘數r（如果a < b，則交換a和b）。
3. 如果餘數r為0，則b就是a和b的GCD。
4. 如果餘數r不為0，則將a和b的值交換，並使用b除以r得到一個新的餘數。
5. 重複步驟3和4，直到餘數為0。

以下是一個使用更相剋除法計算GCD的Python示例：

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)

這個算法的時間複雜度是O(log(min(a, b)))，因為它最多需要log(min(a, b))次除法操作。