93.md

Python 程序：查找 HCF 或 GCD

原文： https://www.programiz.com/python-programming/examples/hcf

在此示例中，您将学习使用两种不同的方法找到两个数字的 GCD：函数和循环，以及欧几里得算法

要理解此示例，您应该了解以下 Python 编程主题：

• Python 函数
• Python 递归
• Python 函数参数

---

两个数字的最高公共因子（HCF）或最大公共除数（GCD）是将两个给定数字完美除的最大正整数。 例如，HCF 为 12 和 14 为 2。

源代码：使用循环

# 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)) 

输出

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。

源代码：使用欧几里得算法

# 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 中交换变量的更多信息。

在每次迭代中，我们将y的值分别放在x中，其余的(x % y)分别放在y中。 当y变为零时，我们得到 HCF。 在x中。