最大公約數怎麼求

最大公約數（Greatest Common Divisor，GCD）是指兩個或多個數的公共除數或因子中的最大值。求最大公約數的方法有很多種，其中最常用的有歐幾里得算法（輾轉相除法）和更相減損法。

歐幾里得算法是一種基於輾轉相除法的求最大公約數的方法。具體步驟如下：

1. 輸入兩個整數a和b，表示要求最大公約數的兩個數。
2. 如果b等於0，那麼最大公約數就是a；否則，繼續執行下一步。
3. 不斷用a除以b的餘數作為新的a，用b作為新的b，直到b等於0為止。
4. 最終得到的a就是最大公約數。

更相減損法也是一種求最大公約數的方法，其基本思路是將兩個數不斷相減，直到其中一個數為0為止，此時另一個數就是最大公約數。

無論使用哪種方法，都可以通過編程實現求最大公約數。例如，在Python中，可以使用以下代碼來求最大公約數：

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

在這個函式中，輸入兩個整數a和b，函式會不斷用b除以a的餘數替換a，直到b為0為止。最終返回的a就是最大公約數。