最大公因數python

在Python中，可以使用math庫中的gcd函式來找到兩個數的最大公因數（GCD）。以下是一個簡單的示例：

import math

def gcd(a, b):
    return math.gcd(a, b)

# 測試
print(gcd(48, 18))  # 輸出: 6

這個函式接受兩個參數a和b，並返回它們的最大公因數。這個函式使用了math庫中的gcd函式，該函式會返回兩個數的最大公因數。

如果你想手動實現這個算法，可以使用歐幾里得算法（Euclidean Algorithm）。以下是一個使用歐幾里得算法的Python實現：

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

# 測試
print(gcd_manual(48, 18))  # 輸出: 6

這個函式使用了一個循環，只要b不為0就一直執行循環。每次循環都會更新a和b的值，直到b等於0為止。這時a就是兩個數的最大公因數。這個方法也是使用歐幾里得算法。