輾轉相除法求最大公約數

輾轉相除法是一種用於求兩個數的最大公約數的方法。這個算法基於這樣一個事實：兩個數的最大公約數等於其中較小的數和兩數的差的最大公約數。以下是使用輾轉相除法求最大公約數的步驟：

1. 設定兩個數 a 和 b，其中 a 是較大的數。
2. 從 a 中減去 b，得到一個新的數 c。
3. 如果 c 不等於 0，那麼重複步驟 2，使用新的數 c 和原來的 b。
4. 當 c 等於 0 時，b 就是最大公約數。

例如，求 48 和 24 的最大公約數：

• 48 - 24 = 24
• 24 - 24 = 0
• 所以，48 和 24 的最大公約數是 24。

Python 中實現輾轉相除法求最大公約數的代碼可以如下：

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

在這個函式中，a 是較大的數，b 是較小的數。在每次循環中，我們將 b 和 a 對 b 取模的結果保存到 a 中，然後 b 就變成了原來的 b（可能已被修改）。當 b 為 0 時，我們就找到了最大公約數，將其返回即可。

例如，使用這個函式求 48 和 24 的最大公約數：

print(gcd(48, 24))  # 輸出：24