# Python 程序：查找 HCF 或 GCD > 原文： [https://www.programiz.com/python-programming/examples/hcf](https://www.programiz.com/python-programming/examples/hcf) #### 在此示例中，您將學習使用兩種不同的方法找到兩個數字的 GCD：函數和循環，以及歐幾里得算法 要理解此示例，您應該了解以下 [Python 編程](/python-programming "Python tutorial")主題： * [Python 函數](/python-programming/function) * [Python 遞歸](/python-programming/recursion) * [Python 函數參數](/python-programming/function-argument) * * * 兩個數字的最高公共因子（HCF）或最大公共除數（GCD）是將兩個給定數字完美除的最大正整數。 例如，HCF 為 12 和 14 為 2。 ## 源代碼：使用循環 ```py # Python program to find HCF of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x > y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The HCF. is", compute_hcf(num1, num2)) ``` **輸出** ```py The HCF. is 6 ``` 在此，將存儲在變量`num1`和`num2`中的兩個整數傳遞給`compute_hcf()`函數。 該函數計算 HCF. 這兩個數字并返回它。 在函數中，我們首先確定兩個數字中較小的一個，因為 HCF 只能小于或等于最小數字。 然后，我們使用`for`循環從 1 轉到該數字。 在每次迭代中，我們檢查我們的數字是否完美地劃分了兩個輸入數字。 如果是這樣，我們將數字存儲為 HCF。 循環結束時，我們得到最大的數字，該數字完美地將兩個數字相除。 上述方法易于理解和實現，但是效率不高。 查找 HCF 的更有效方法是歐幾里得算法。 ## 歐幾里得算法 該算法基于輾轉相除計算 HCF。 在此算法中，我們將較大除以較小，然后取余數。 現在，將較小的除以該余數。 重復直到剩余為 0。 例如，如果我們想找到 HCF. 54 和 24 中的 54，我們將 54 除以 24。余數為 6。現在，我們將 24 除以 6，余數為 0。因此，6 是所需的 HCF。 ## 源代碼：使用歐幾里得算法 ```py # Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf) ``` 在這里我們循環直到`y`變為零。 語句`x, y = y, x % y`在 Python 中進行值交換。 單擊此處以了解有關在 Python 中交換[變量的更多信息](/python-programming/examples/swap-variables "Source Code to Swap Variables")。 在每次迭代中，我們將`y`的值分別放在`x`中，其余的`(x % y)`分別放在`y`中。 當`y`變為零時，我們得到 HCF。 在`x`中。