在 Python 中實現最大公約數操作

1. 在 Python 中使用遞迴實現 GCD 的程式碼
2. 在 Python 中使用 for 迴圈實現最大公約數的程式碼
3. 在 Python 中使用歐幾里德演算法實現最大公約數的程式碼
4. 在 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 開始，它現在已被棄用。