跳到主要内容

Python 程序：查找最高公因数或最大公约数

要理解这个示例，你需要了解以下Python编程主题的知识：

两个数的最大公约数（H.C.F）或最大公因数（G.C.D）是能够完美整除这两个给定数的最大正整数。例如，12和14的H.C.F是2。

源代码：使用循环​

# Python程序：查找两个数的H.C.F
# 定义一个函数
def compute_hcf(x, y):

# 选择较小的数
    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("最大公约数是", compute_hcf(num1, num2))

输出

最大公约数是 6

这里，两个整数存储在变量num1和num2中，传递给compute_hcf()函数。该函数计算这两个数的H.C.F并返回它。

在函数中，我们首先确定两个数中较小的一个，因为H.C.F只能小于或等于最小的数。然后我们使用for循环从1循环到那个数。

在每次迭代中，我们检查我们的数是否能够完美地整除两个输入数。如果是，我们将该数存储为H.C.F。循环完成时，我们得到了能够完美整除两个数的最大数。

上述方法易于理解和实现，但效率不高。找到H.C.F的一个更有效的方法是欧几里得算法。

欧几里得算法​

这个算法基于一个事实：两个数的H.C.F也能够整除它们的差值。

在这个算法中，我们将较大的数除以较小的数，并取余数。现在，将较小的数除以这个余数。重复直到余数为0。

例如，如果我们想找54和24的H.C.F，我们将54除以24。余数是6。现在，我们将24除以6，余数是0。因此，6是所需的H.C.F。

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

# 使用欧几里得算法查找HCF的函数
def compute_hcf(x, y):
    while(y):
        x, y = y, x % y
    return x

hcf = compute_hcf(300, 400)
print("最大公约数是", hcf)

这里我们循环直到y变为零。Python中的语句x, y = y, x % y用于交换值。点击此处了解更多关于在Python中交换变量的信息。

在每次迭代中，我们将y的值放在x中，同时将余数(x % y)放在y中。当y变为零时，我们在x中得到H.C.F。

最后于 更新