C求最大公因數

求兩個數的最大公因數（Greatest Common Divisor, GCD）有很多種方法，這裡介紹一種簡單的算法——歐幾里得算法（Euclidean algorithm），又稱為輾轉相除法。

假設我們要找出兩個正整數a和b的最大公因數。

1. 首先，我們用a除以b，得到一個餘數c。如果b除以c的餘數為0，那麼c就是a和b的最大公因數。

2. 如果b除以c的餘數不是0，我們換成用b除以c，得到一個餘數d。

3. 重複上述步驟，直到其中一個數為0。此時，另一個數就是它們的最大公因數。

以下是一個簡單的例子：

a = 12
b = 18

18 ÷ 12 = 1 R 6
12 ÷ 6 = 2 R 0

所以，12和18的最大公因數是6。

在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: "))
print(f"The greatest common divisor of {a} and {b} is {gcd(a, b)}.")

這段代碼會提示用戶輸入兩個數，然後計算它們的最大公因數並列印出來。