最大公約數算法很無聊嗎？輾轉相除法3行代碼搞定

最大公約數算法不是很無聊，計算最大公約數是數學中一個重要的概念，可以用于判斷兩個數是否互質、求分數的約分等，在很多領域都有廣泛的應用。具體如下：

1. 判斷兩個數是否互質：兩個數的最大公約數為1，說明這兩個數是互質的。
2. 求分數的約分：將分子和分母的最大公約數約分掉，使得分數的值不變。
3. 求同余方程的最小正整數解：例如求ax ≡ b (mod m) 的最小正整數解。
4. 求兩個數的最小公倍數：兩個數的乘積除以它們的最大公約數。
5. 判斷數的因數：通過求數的最大公約數判斷是否為該數的因數。

最大公約數（Greatest Common Divisor, GCD）算法是求兩個或多個整數的最大公因數的方法。常用的算法有輾轉相除法、更相減損術、窮舉法、質因數分解法等。

輾轉相除法：

• 如果兩個整數不相等，則將大數除以小數，將余數代替較小數再進行同樣的除法操作。
• 重復上述操作，直到兩個數相等，則兩個數的最大公約數就是這兩個數。

更相減損術：

• 將兩個數中的較大數減去較小數，再把差代替較大數，進行同樣的減法操作。
• 重復上述操作，直到兩個數相等，則兩個數的最大公約數就是這兩個數。

窮舉法：

• 從1到較小數遍歷，判斷是否是兩個數的公因數，如果是則記錄。
• 得到的公因數中，最大的即為兩個數的最大公約數。

質因數分解法：

• 將兩個數的質因數分解，并列出它們的公因數。
• 公因數中的最大值即為兩個數的最大公約數。

下面是最大公約數算法的 Python 代碼示例：

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

這是一種輾轉相除法求最大公約數的方法，它每次通過計算余數，來降低計算復雜度。