計算並獲得Python中的最大公約數和最小公約數

商業

下面介紹如何在 Python 中計算和獲取最大公約數和最小公約數。

  • 兩個整數的最大公約數和最小公倍數
  • 三個或更多整數的最大公約數和最小公倍數

請注意，標準庫中提供的函數規格因 Python 版本而異。本文還展示了一個不在標準庫中的函數的示例實現。

  • Python 3.4 或更早版本
    • GCD:fractions.gcd()（只有兩個論點）
  • Python 3.5 或更高版本
    • GCD:math.gcd()（只有兩個論點）
  • Python 3.9 或更高版本
    • GCD:math.gcd()（支持三個以上的參數）
    • 最小公分母:math.lcm()（支持三個以上的參數）

這裡我們解釋一下使用標準Python庫的方法； NumPy 可以很容易地用於計算多個數組的每個元素的最大公約數和最小公約數。

兩個整數的最大公約數和最小公倍數

GCD

從 Python 3.5 開始，數學模塊中有一個 gcd() 函數。 gcd() 是

  • greatest common divisor

返回參數中指定的整數的最大公約數。

import math

print(math.gcd(6, 4))
# 2

請注意，在 Python 3.4 及更早版本中，gcd() 函數位於分數模塊中，而不是數學模塊中。必須導入分數和fractions.gcd()。

最小公分母

返回最小公倍數的 lcm() 函數被添加到 Python 3.9 的數學模塊中。 lcm 是的首字母縮寫詞

  • least common multiple

返回參數中指定的整數的最小公倍數。

print(math.lcm(6, 4))
# 12

在 Python 3.8 之前，不提供 lcm()，但可以使用 gcd() 輕鬆計算。

lcm(a, b) = a * b / gcd(a, b)

實施示例。

def my_lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(my_lcm(6, 4))
# 12

/由於這會導緻小數浮點數，因此使用兩個反斜杠截斷小數點並返回整數除法結果。請注意，不進行任何處理來確定參數是否為整數。

三個或更多整數的最大公約數和最小公倍數

Python 3.9 或更高版本

從 Python 3.9 開始，以下所有函數都支持三個以上的參數。

  • math.gcd()
  • math.lcm()
print(math.gcd(27, 18, 9))
# 9

print(math.gcd(27, 18, 9, 3))
# 3

print(math.lcm(27, 9, 3))
# 27

print(math.lcm(27, 18, 9, 3))
# 54

*如果要計算列表元素的最大公約數或最小公約數，請使用 this 指定參數。

l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3

print(math.lcm(*l))
# 54

Python 3.8 或更早版本

在 Python 3.8 之前， gcd() 函數僅支持兩個參數。

求三個或更多整數的最大公約數或最小公倍數，不需要特別複雜的算法；只需使用高階函數 reduce() 依次計算多個值中的每個值的最大公約數或最小公約數。

GCD

from functools import reduce

def my_gcd(*numbers):
    return reduce(math.gcd, numbers)

print(my_gcd(27, 18, 9))
# 9

print(my_gcd(27, 18, 9, 3))
# 3

l = [27, 18, 9, 3]
print(my_gcd(*l))
# 3

再次注意，在 Python 3.4 之前，gcd() 函數位於分數模塊中，而不是數學模塊中。

最小公分母

def my_lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def my_lcm(*numbers):
    return reduce(my_lcm_base, numbers, 1)

print(my_lcm(27, 9, 3))
# 27

print(my_lcm(27, 18, 9, 3))
# 54

l = [27, 18, 9, 3]
print(my_lcm(*l))
# 54
Copied title and URL