Python 最高公因數 (HCF / GCD)
使用歐幾里德演算法計算兩個數字的最高公約數 (HCF) 或最大公約數 (GCD)。
概述
最高公因數 (HCF)，也稱為最大公約數 (GCD)，是兩個或多個整數相除不留餘數的最大正整數。
歐幾裡得演算法是計算 HCF 的極為有效的方法。它指出兩個數字的 GCD 也可以除以它們的差。
在 Python 中，我們使用 while 循環迭代地實現這一點，其中我們不斷地將較大的數字替換為除法的餘數。
程式碼和執行輸出
歐幾里德循環實現找出兩個數字的 HCF/GCD。
hcf_gcd.py
在編輯器中嘗試def find_gcd(a, b):
# Euclidean Algorithm
while b != 0:
a, b = b, a % b
return a
print("GCD of 36 and 60 is:", find_gcd(36, 60))
print("GCD of 17 and 5 is: ", find_gcd(17, 5))端子輸出
GCD of 36 and 60 is: 12
GCD of 17 and 5 is: 1逐步實施
- 分數簡化和數學引擎
- 加密演算法（如 RSA 私鑰產生）
- 設計定期活動時間表
常見問題解答
Python有內建的GCD函數嗎？
是的！ Python 的標準函式庫包含 `math.gcd(a, b)`，它在底層使用編譯的 C 實作。