在 Python 中实现最大公约数操作
- 在 Python 中使用递归实现 GCD 的代码
-
在 Python 中使用
for
循环实现最大公约数的代码 - 在 Python 中使用欧几里德算法实现最大公约数的代码
-
在 Python 中使用
math.gcd()
函数计算最大公约数
最大公约数 (GCD),也称为两个值的最高公因数 (HCF),是将两个给定数相除的最大数。最大公约数也可以用 Python 计算和实现。
本教程演示了在 Python 中实现最大公约数的代码的不同方法。
在 Python 中使用递归实现 GCD 的代码
在函数定义块中调用自身的函数称为递归。递归可用于创建计算两个数字的 GCD
的函数。这个过程对于减少代码长度非常有用,并且可以方便地减少不必要的函数调用。
下面的代码使用递归来实现 Python 中最大公约数的代码。
def gcd1(x, y):
if(y==0):
return x
else:
return gcd1(y,x%y)
x = 72
b= 60
print ("The gcd is : ",end="")
print (gcd1(72,60))
上面的程序给出了以下结果。
输出:
The gcd is : 12
在 Python 中使用 for
循环实现最大公约数的代码
一个简单的 for
循环和 if-else
语句可以帮助实现与本文中的其他方法相同的任务。
以下代码使用 for
循环来实现 Python 中最大公约数的代码。
def gcd2(a, b):
if a > b:
small = b
else:
small = a
for i in range(1, small+1):
if((a % i == 0) and (b % i == 0)):
gcd = i
return gcd
a = 72
b = 60
print ("The gcd is : ",end="")
print (gcd2(72,60))
上面的代码给出了以下结果。
输出:
The gcd is : 12
在 Python 中使用欧几里德算法实现最大公约数的代码
欧几里得算法是另一种能够快速计算两个数的最大公约数的技术。
欧几里得算法是根据两个主要事实来定义的。
- 如果较小的数字减去较大的数字,则 GCD 没有变化。因此,我们最终找到了两个数字中较大值的继续减法的 GCD。
- 如果我们除以较小的数,而不是在此处进行减法,算法会在遇到余数
0
时自动停止。
下面的程序使用欧几里得算法来实现 Python 中最大公约数的代码。
def gcd3(p, q):
while(q):
p, q = q, p % q
return p
p = 72
q = 60
print ("The gcd is : ",end="")
print (gcd3(72,60))
该代码提供了以下结果。
输出:
The gcd is : 12
在 Python 中使用 math.gcd()
函数计算最大公约数
现在,我们可以简单地使用预定义的 math.gcd()
函数来计算两个数字的 GCD,而不是创建用户定义的函数。math
模块需要导入到 Python 代码中才能使用 gcd()
函数。
以下代码使用 math.gcd()
函数来计算 Python 中的最大公约数。
import math
a = math.gcd(72,60)
print(a)
上面的程序提供了以下结果。
输出:
12
在 Python 3.5 及更高版本中,gcd
函数包含在 math
模块中。在早期的 Python 版本中,gcd
函数包含在 fractions
模块中。但是,从 Python 3.5 开始,它现在已被弃用。
Vaibhhav is an IT professional who has a strong-hold in Python programming and various projects under his belt. He has an eagerness to discover new things and is a quick learner.
LinkedIn