寻找 HCF(最大公因数) 或 GCD(最大公约数) 的 Python 程序

在这个例子中，你将学习使用两种不同的方法找到两个数字的 GCD: 函数和循环以及欧几里得算法
为了理解这个例子，你应该了解下面的 Python 编程主题:

Python Functions 函数
Python Recursion 4. Python 递归
Python Function Arguments 函数参数
两个数的最高公因数(H.C.F)或最大公约数(G.C.D)是完全除以两个给定数的最大正整数。例如，12和14的 H.C.F 是2。

源代码: Using loop

# Python program to find H.C.F 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 H.C.F. is", compute_hcf(num1, num2))

输出

The H.C.F. is 6

这里，存储在变量 num1和 num2中的两个整数被传递给 compute _ hcf()函数。
在函数中，我们首先确定两个数中较小的一个，因为 H.C.F 只能小于或等于最小数。然后我们使用 for 循环从1到这个数。
在每次迭代中，我们检查我们的数字是否完全除以两个输入数字。如果是这样，我们将数字存储为 h.c.f。在循环结束时，我们得到了最大的一个数，这个数完全地除以这两个数。
上述方法易于理解和实现，但效率不高。一个更有效的方法是欧几里得算法。

欧几里得算法

该算法基于 H.C.F. 两个数除以它们的差。
在这个算法中，我们用较大的除以较小的，然后取得余数。现在，用小数除以这个余数，重复直到余数为0。
例如，如果我们想找到 H.C.F. 在 54 和 24 中，我们将 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("The HCF is", hcf)

在这里我们循环直到 y 变为零。语句 x，y = y，x% y 在 Python 中进行值交换。