Python 如何找到最大公因数（HCF）或最大公约数（GCD）

在本文中，我们将展示如何在Python中找到HCF（最大公因数）或GCD（最大公约数）。以下是实现此任务的各种方法：

使用for循环
使用欧几里得算法
使用while循环
使用递归（原生方法）
处理HCF中的负数

什么是H.C.F.或G.C.D

能够完全整除两个给定数字的最大正整数称为最大公因数（H.C.F.）或最大公约数（G.C.D.）。

示例 - 12和14的HCF是2。

使用for循环

步骤

以下是执行所需任务的算法/步骤：

创建一个变量来存储输入的第一个数字。
创建另一个变量来存储输入的第二个数字。
使用if条件语句来检查第一个数字是否大于第二个数字。
如果条件为真，则将第二个数字视为较小的数字。
否则将第一个数字视为较小的数字。
使用for循环遍历从1到较小数字的范围（range()函数返回从0开始以1（默认）递增，并在给定数字之前停止的数列）。
使用if条件语句来检查第一个和第二个数字是否可以被索引（i）整除，使用取模运算符（返回余数）和操作符（如果两个条件都为真，则返回true）。
如果条件为真，则将相应的索引（i）值分配为HCF。
打印输入的第一个数字和第二个数字的结果HCF。

示例

以下程序使用for循环返回了输入的第一个数字和第二个数字的HCF-

# input number 1
inputNumber_1 = 30
# input number 2
inputNumber_2 = 14
# checking whether the first number is greater than
# the second one
if inputNumber_1 > inputNumber_2:
   # assigning the second number as a smaller number
   small_num = inputNumber_2
else:
   # else assigning the first number as a smaller number
   small_num = inputNumber_1
# traversing from 1 to the small number range
for i in range(1, small_num+1):
   # checking whether both the first and second numbers divide exactly by index (i)
   if((inputNumber_1 % i == 0) and (inputNumber_2 % i == 0)):
      # assigning the index(i) value as HCF if the condition is true
      resultHcf = i
# printing the HCF of input number 1 & input number 2
print("The H.C.F of", inputNumber_1, "and", inputNumber_2, "=", resultHcf)

输出

执行上面的程序将生成以下输出-

The H.C.F of 30 and 14 = 2

使用欧几里德算法

示例

以下程序使用欧几里德算法返回输入数字1和输入数字2的最大公约数—

# creating a function that returns the HCF of two numbers passed to it
def calculateHcf(p, q):
   # traversing the loop until q times
   while(q):
      # assigning q value to p, p % q value to q
      p, q = q, p % q
   # returning p value(i.e, inputNumber_2)
   return p
# input number 1
inputNumber_1 = 15
# input number 2
inputNumber_2 = 4
# calling the calculateHcf() function by passing both the input numbers to it
resultHcf = calculateHcf(inputNumber_1, inputNumber_2)
# printing the HCF of input number 1 & input number 2
print("The H.C.F of", inputNumber_1, "and", inputNumber_2, "=",
calculateHcf(inputNumber_1, inputNumber_2))

输出

执行上述程序后，将生成以下输出–

The H.C.F of 15 and 4 = 1

使用while循环（重复减法）

示例

下面的程序使用while循环（重复减法方法）返回输入数字1和输入数字2的最大公约数 –

# input number 1
inputNumber_1 = 40
# input number 2
inputNumber_2 = 5
# storing both the numbers in temporary variables
# for not getting disturbed
temp_1 = inputNumber_1
temp_2 = inputNumber_2
# traversing the loop until both the numbers are not equal
while inputNumber_1 != inputNumber_2:
   # checking whether inputNumber_1 is greater than inputNumber_2
   if inputNumber_1 > inputNumber_2:
      # assigning inputNumber_1-inputNumber_2 value to inputNumber_1
      inputNumber_1 -= inputNumber_2
   else:
      # else assigning inputNumber_2-inputNumber_1 value to inputNumber_2
      inputNumber_2 -= inputNumber_1
# printing the HCF of input number 1 & input number 2
print("The H.C.F of", temp_1, "and", temp_2, "=", inputNumber_1)

输出

执行上述程序后，会产生以下输出：

The H.C.F of 40 and 5 = 5

使用递归（原生方法）

示例

以下程序使用递归返回输入数字1和输入数字2的最大公约数 –

# creating a function that returns the HCF of two numbers passed to it
def calculateHcf(num_1, num_2):
   # checking whether the second number is equal to 0
      if(num_2 == 0):
         # returning the absolute value of the first number if the condition is true
         return abs(num_1)
      else:
         # else returning the resultant HCF by calling the calculateHcf() function
         # by passing num_2, value of num_1 % num_2 as arguments
         return calculateHcf(num_2, num_1 % num_2)
# input number 1
inputNumber_1 = 32
# input number 2
inputNumber_2 = 6
# calling the calculateHcf() function by passing both the input numbers to it
print("The H.C.F of", inputNumber_1, "and", inputNumber_2, "=",
calculateHcf(inputNumber_1, inputNumber_2))

输出

执行上述程序后，将生成以下输出 –

The H.C.F of 32 and 6 = 2

处理最大公因数中的负数

两个数的最大公因数永远不能是负数，所以如果其中任何一个数是负数，将它们乘以-1使其变为正数。

使用欧几里得算法中的取模运算符(%)有效地改进了重复减法的复杂性。

以下程序使用while处理最大公因数中的负数，返回输入的第一个数和第二个数的最大公因数 –

示例

# creating a function to calculate the hcf
def calculateHcf(x, y):
   return y == 0 and x or calculateHcf(y, x % y)
# input number 1
inputNumber_1 = -4
# input number 2
inputNumber_2 = 15
# If the user types a negative number, we simply change it to a positive number.
# HCF is the highest positive number that divides both numbers
# -4 & 15 --> HCF = 1 (as the highest number that divides both)
# -4 & -15 --> HCF = 1 (as the highest number that divides both)
inputNumber_1 >= 0 and inputNumber_1 or -inputNumber_1
inputNumber_2 >= 0 and inputNumber_2 or -inputNumber_2
# calling the calculateHcf() function by passing both the input numbers to it
print("The H.C.F of", inputNumber_1, "and", inputNumber_2, "=",
calculateHcf(inputNumber_1, inputNumber_2))