轉相除法如何計算最大公因數

輾轉相除法是一種用於計算兩個數字的最大公因數（GCD）的算法。這種方法基於這樣一個事實：兩個數字的最大公因數等於其中較小的數字和兩數相除後所得餘數的最大公因數。

以下是輾轉相除法的基本步驟：

1. 輸入兩個數字，比如我們用a和b表示。
2. 設定一個變數temp，初始值為a。
3. 進行以下循環，直到temp等於0：

a. 將temp除以b，並將餘數賦給temp（如果餘數不為0，則說明b是a和這兩個數的最大公因數）。

b. 將a賦給b。 4. 返回temp，這就是a和b的最大公因數。

以下是對應的Python代碼實現：

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

這段代碼的工作原理是反覆將較大的數除以較小的數，直到餘數為0。在每次循環中，較大的數都會變為原來的較小數，而較小數則變為原來的較大數和餘數的乘積。當餘數為0時，此時的最大公因數就是原來的較大數。所以最終循環結束後返回的a就是我們要找的最大公因數。