Python程序查找最大公因数（HCF）或最大公约数（GCD）
在此示例中，您将学习使用两种不同的方法查找两个数字的GCD：函数和循环以及欧几里得算法
要理解此示例，您应该了解以下Python编程主题：
两个数的最大公因数(H.C.F)或最大公约数(G.C.D)是能完美地将两个给定数相除的最大正整数。例如，H.C.F(12, 14)等于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("H.C.F. 是", compute_hcf(num1, num2))
输出结果
H.C.F. 是 6
这里，存储在变量num1和num2中的两个整数被传递给compute hcf()函数。该函数计算H.C.F.这两个数字并返回它。
在这个函数中，我们首先确定两个数字中较小的那个F只能小于或等于最小的数。然后我们使用一个for循环从1到那个数字。
在每次迭代中，我们检查我们的数字是否完美地将两个输入数字相除。如果是这样，我们将这个数字存储为H.C.F.，在循环结束时，我们得到的最大的数字完美地将两个数字相除。
上述方法易于理解和实施，但是效率不高。查找HCF的一种更有效的方法是欧几里得算法。
欧几里得算法
该算法基于以下事实：两个数字的HCF也将它们的差除。
在此算法中，我们将较大者除以较小者，然后取余数。现在，将较小者除以该余数。重复直到剩余为0。
例如，如果我们想求54和24的hcf，我们用54除以24。余数是6。24除以6，余数是0。因此，6是必需的hcf
源代码：使用欧几里得算法
# 函数查找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中交换值。单击此处以了解有关在Python中交换变量的更多信息。
在每次迭代中，我们同时将y的值放在x中，其余的(x % y)放在y中。当y变为0时，我们得到x的hcf。
发表评论