用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模块中，而不是数学模块中。必须导入fractions和fractions.gcd()。

最小公分母

lcm()函数，返回最小公倍数，在Python 3.9中被添加到数学模块。

  • 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

*如果你想计算一个列表中的元素的最大公除数或最小公倍数，用这个参数指定。

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