您的位置:

Python 中两个数字的 GCD

最大公约数 (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

输出: