用于求最大公约数（HCF 或 GCD）的 Python 程序

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

源代码：使用循环

# 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() 函数。该函数计算这两个数的最大公因数并返回。

在该函数中，我们首先确定两个数中较小的一个，因为最大公因数只能小于或等于最小的数。然后我们使用 for 循环从 1 到那个数进行迭代。

在每次迭代中，我们检查当前数是否能完美地整除两个输入数。如果能，我们就将该数存储为最大公因数。循环完成后，我们最终得到能完美地整除这两个数的最大数。

上述方法易于理解和实现，但效率不高。一种更有效的方法来寻找最大公因数是欧几里得算法。

欧几里得算法

该算法基于这样一个事实：两个数的最大公因数也能整除它们的差。

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

例如，如果我们想找到 54 和 24 的最大公因数，我们用 54 除以 24。余数是 6。现在，我们用 24 除以 6，余数是 0。因此，6 是所需的最大公因数。

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

# 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 变为零时，x 中就是最大公因数。

另请阅读

• Python 程序：求最小公倍数 (LCM)