在 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 開始，它現在已被棄用。