# 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`中。