歐幾里德如何求最大公約數

歐幾里德算法（也被稱為輾轉相除法）是一種用於求兩個整數的最大公約數（GCD）的算法。該算法基於以下原理：兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數。具體步驟如下：

1. 將較小的數賦值給較大的數。
2. 從第二個數中減去第一個數，並除以較小的數，將餘數（假設為a）賦值為新的被除數，並將新的除數賦值給第一個數。
3. 重複步驟2，直到餘數為0，此時，原來的被除數（最後一個）就是最大公約數。

算法的關鍵在於不斷地把除數與被除數進行比較，並將較大的數賦值給較小的數，以實現疊代的過程。這個過程直到餘數為0為止，此時較大的數就是兩個數的最大公約數。

在Python中，可以使用以下代碼實現歐幾里德算法：

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

在這個函式中，輸入參數a和b是兩個整數，函式返回它們的最大公約數。這個函式會一直循環執行，直到b變為0為止。每次循環中，將b賦值給a，將a除以b的餘數賦值給b。當b變為0時，函式返回結果。