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

輸出: