如何使用Python查找HCF或GCD？

本文将展示如何使用Python查找 HCF （最大公因数）或 GCD （最大公约数）。下面是完成此任务的各种方法：

使用For循环
使用欧几里得算法
使用While循环
使用递归（朴素方法）
处理HCF中的负数

阅读更多：Python 教程

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

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

示例 - 12和14的HCF为 2 。

使用For循环

算法（步骤）

请按照以下步骤执行所需任务：

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

示例

以下程序使用for循环返回输入数字1和输入数字2的HCF –

# 输入数字1
inputNumber_1 = 30
# 输入数字2
inputNumber_2 = 14
# 检查第一个数字是否大于
# 第二个数字
if inputNumber_1 > inputNumber_2:
   # 将第二个数字视为较小的数字
   small_num = inputNumber_2
else:
   # 将第一个数字视为较小的数字
   small_num = inputNumber_1
# 遍历从1到小数字的range
for i in range(1, small_num+1):
   #检查第一个和第二个数字是否能够被索引（i）完全除尽
   if((inputNumber_1 % i == 0) and (inputNumber_2 % i == 0)):
      #如果条件满足，则将索引（i）值分配为HCF
      resultHcf = i
#打印输入数字1和输入数字2的HCF
print("The H.C.F of", inputNumber_1, "and", inputNumber_2, "=", resultHcf)

输出

在执行时，上述程序将生成以下输出−

30和14的H.C.F = 2

使用欧几里得算法

例子

以下程序返回使用欧几里得算法的输入数字1和输入数字2的HCF –

#创建一个函数，返回传递给它的两个数字的HCF
def calculateHcf(p, q):
   #循环遍历直到q次
   while(q):
      #将q值赋值给p，将p％q值赋值给q
      p, q = q, p % q
   #返回p值（即inputNumber_2）
   return p
#输入数字1
inputNumber_1=15
#输入数字2
inputNumber_2=4
#通过将两个输入数字传递给它来调用calculateHcf（）函数
resultHcf=calculateHcf(inputNumber_1,inputNumber_2)
#打印输入数字1和输入数字2的HCF
print("The H.C.F of",inputNumber_1,"and",inputNumber_2,"=",
calculateHcf(inputNumber_1,inputNumber_2))

输出

在执行时，上述程序将生成以下输出−

15和4的H.C.F = 1

使用while循环（重复减法）

例子

以下程序使用while循环（重复减法方法）返回输入数字1和输入数字2的HCF –

#输入数字1
inputNumber_1=40
#输入数字2
inputNumber_2=5
#将两个数字存储在临时变量中
#不要受干扰
temp_1=inputNumber_1
temp_2=inputNumber_2
#遍历循环，直到两个数字都不相等
whileinputNumber_1!=inputNumber_2:
   #检查inputNumber_1是否大于inputNumber_2
   ifinputNumber_1>inputNumber_2:
      #将inputNumber_1-inputNumber_2的值分配给inputNumber_1
      inputNumber_1-=inputNumber_2
   else:
      #否则将inputNumber_2-inputNumber_1的值分配给inputNumber_2
      inputNumber_2-=inputNumber_1
#打印输入数字1和输入数字2的HCF
print("The H.C.F of",temp_1,"and",temp_2,"=",inputNumber_1)

输出

在执行时，上述程序将生成以下输出−

40和5的H.C.F = 5

使用递归（朴素方法）

例子

以下程序使用递归返回输入数字1和输入数字2的HCF –

# 创建一个函数，返回传递给它的两个数的最大公因数（HCF）
def calculateHcf(num_1， num_2):
   # 检查第二个数字是否等于0
      if(num_2 == 0):
         # 如果条件为真，则返回第一个数字的绝对值
         return abs(num_1)
      else:
         # 否则通过传递num_2，num_1％num_2的值作为参数来调用calculateHcf（）函数来返回结果HCF
         return calculateHcf(num_2， num_1 % num_2)
# 输入数字1
inputNumber_1 = 32
# 输入数字2
inputNumber_2 = 6
# 通过将两个输入数字传递给它来调用calculateHcf（）函数
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

处理HCF中的负数

两个数字的HCF永远不会是负数，因此如果任何一个数字是负数，只需将它们乘以-1使它们变为正数即可。

在此方法中，通过在欧几里得算法中有效使用取模运算符（％），可以改善重复减法的复杂性。

以下程序返回输入数字1＆amp;输入数字2的HCF，使用while处理HCF中的负数-

示例

# 创建函数以计算hcf
def calculateHcf(x， y):
   return y == 0 and x or calculateHcf(y， x % y)
# 输入数字1
inputNumber_1 = -4
# 输入数字2
inputNumber_2 = 15
# 如果用户键入负数，则只需将其更改为正数即可。
# HCF是除两个数字的最高正数
# -4＆15  - > HCF = 1（因为除两者的最高数字）
# -4＆-15  - > HCF = 1（因为除两者的最高数字）
inputNumber_1 >= 0 and inputNumber_1 or -inputNumber_1
inputNumber_2 >= 0 and inputNumber_2 or -inputNumber_2
# 通过将两个输入数字传递给它来调用calculateHcf（）函数
print("The H.C.F of"， inputNumber_1， "and"， inputNumber_2， "="，
calculateHcf(inputNumber_1， inputNumber_2))