最大公约数 (GCD)是一个数学术语，用来寻找可以完美划分两个数的最大公因数。GCD 也被称为最高共同因子(HCF) 。例如，两个数字 54 和 24 的 HCF/ GCD 是 6。因为 6 是完全除 54 和 24 的最大公约数。
使用 gcd()函数的 GCD
在 python 中，gcd()是math模块提供的一个内置函数，用于查找两个数字的最大公约数。
语法
gcd(a, b)
其中 a 和 b 是作为参数传递给函数 gcd()的两个整数。
让我们创建一个程序，使用 python 中 math.gcd()的内置函数打印两个数字的 GCD。
math_fun.py
# create a program to print the gcd of two number in python using the math.gcd() function.
import math
print(" GCD of two number 0 and 0 is ", math.gcd(0, 0)) #math.gcd(a, b), a and b are the two integer number
print(" GCD of two number 0 and 48 is ", math.gcd(0, 48))
a = 60 # assign the number to variable a
b = 48 # assign the number to variable b
print(" GCD of two number 60 and 48 is ", math.gcd(a, b)) # pass the variable a and b to math.gcd() function.
print(" GCD of two number 48 and -12 is ", math.gcd(48, -12)) # pass the integer number
print(" GCD of two number -24 and -18 is ", math.gcd(-24, -18))
print(" GCD of two number -60 and 48 is ", math.gcd(-60, 48))
输出:
在上面的例子中，math.gcd()函数生成两个给定数字的 gcd。在 gcd()函数中，a 和 b 作为一个参数传递，返回两个整数的最大公约数，将数字完全除。
使用递归的 GCD
递归是 python 中定义的内存消耗函数，它通过自引用表达式调用自己。这意味着函数将不断地调用和重复自己，直到满足定义的条件，以返回该数的最大公约数。
算法的伪代码
步骤 1:从用户那里获取两个输入，x 和 y。
步骤 2:将输入数字作为参数传递给递归函数。
第三步:如果第二个数等于零(0)，则返回第一个数。
步骤 4:否则，它递归调用以第二个数字作为参数的函数，直到得到余数，余数将第二个数字除以第一个数字。
第五步:调用 gcd_fun()或者给变量赋值。
第六步:显示两个数字的 GCD。
第七步:退出程序。
让我们理解用递归求两个数的 GCD 的程序。
gcdreur . py
# write a program to understand the GCD of two number in python using the recursion.
def gcd_fun (x, y):
if (y == 0): # it divide every number
return x # return x
else:
return gcd_fun (y, x % y)
x =int (input ("Enter the first number: ")) # take first no.
y =int (input ("Enter the second number: ")) # take second no.
num = gcd_fun(x, y) # call the gcd_fun() to find the result
print("GCD of two number is: ")
print(num) # call num
输出:
使用循环的 GCD
让我们创建一个程序，使用循环在 python 中找到两个数字的 GCD。
gcdFile.py
def GCD_Loop( a, b):
if a > b: # define the if condition
temp = b
else:
temp = a
for i in range(1, temp + 1):
if (( a % i == 0) and (b % i == 0 )):
gcd = i
return gcd
x = int(input (" Enter the first number: ") ) # take first no.
y =int (input (" Enter the second number: ")) # take second no.
num = GCD_Loop(x, y) # call the gcd_fun() to find the result
print("GCD of two number is: ")
print(num) # call num
输出:
正如我们在上面的程序中看到的，我们将两个值作为输入，并将这些数字传递给 GCD_Loop()函数，以返回一个 GCD。
使用欧几里德算法或欧几里德算法的几何中心
欧几里德算法是求两个数最大公约数的有效方法。这是最古老的算法，它将较大的数分成较小的数，然后取余数。同样，它从余数中除以较小的数，并且该算法连续地除以该数，直到余数变为 0。
例如，假设我们要计算两个数字，60 和 48 的高频。然后我们把 60 除以 48；它返回余数 12。现在我们再次用数字 24 除以 12，然后它返回余数 0。这样，我们得到的氢氟碳化合物是 12。
欧几里德算法的伪码
第一步:有两个整数，比如 a 和 b。
第二步:如果 a = 0，那么 GCD(a，b)就是 b。
第三步:如果 b = 0，则 GCD(a，b)为 a。
第四步:找到
第五步:假设 a = b，b = R
步骤 6:重复步骤 4 和 3，直到 mod b 等于或大于 0。
第七步:GCD = b 然后打印结果。
第八步:停止程序。
让我们使用 python 中的欧几里德算法来找到两个数的 H.C.F 或 GCD。
Euclid.py
# Create a program to find the GCD of two number in python using the Euclid's Algorithm.
def find_hcf(a,b):
while(b):
a, a = b, a % b
return a
a = int(input (" Enter the first number: ") ) # take first no.
b = int(input (" Enter the second number: ")) # take second no.
num = find_hcf(a, b) # call the find_hcf() to get the result
print(" The HCF of two number a and b is ")
print(num) # call num
输出: