如何求兩正整數的最大公因數

求兩個正整數的最大公因數（Greatest Common Divisor, GCD）可以使用質因數分解法、歐幾里得算法（Euclidean algorithm）或輾轉相除法等方法。這裡我們主要介紹歐幾里得算法，因為它是最常用的方法之一，而且適用於任何正整數。

歐幾里得算法的步驟如下：

1. 設兩個正整數為 ( a ) 和 ( b )，其中 ( a > b )。
2. 計算 ( a ) 除以 ( b ) 的餘數，記作 ( r = a \bmod b )。
3. 如果 ( r ) 為0，則 ( b ) 就是 ( a ) 和 ( b ) 的最大公因數；否則，將 ( b ) 賦值給 ( a )，將 ( r ) 賦值給 ( b )，並回到第二步繼續計算。

以下是一個使用歐幾里得算法求兩個正整數最大公因數的例子：

輸入兩個正整數 a 和 b，求它們的最大公因數。
a = 12, b = 8

12 ÷ 8 = 1, 餘數 r = 4
將 b 賦值給 a，將 r 賦值給 b
a = 8, b = 4

8 ÷ 4 = 2, 餘數 r = 0
因為 r = 0，所以 b（現在為 4）就是 a 和 b 的最大公因數。

最大公因數 GCD(12, 8) = 4

在編程中，可以使用一個循環來實現歐幾里得算法，直到餘數為0為止。以下是一個簡單的Python程式碼示例：

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

# 使用例子
a = int(input("請輸入第一個正整數："))
b = int(input("請輸入第二個正整數："))
gcd_value = gcd(a, b)
print("兩數的最大公因數是：", gcd_value)

這個程式碼會提示用戶輸入兩個正整數，並使用上面的 gcd 函數來計算它們的最大公因數。