Pythonで最大公約数と最小公倍数を算出・取得

Modified: | Tags: Python, 算数・数学

Pythonで最大公約数と最小公倍数を算出・取得する方法について説明する。

Pythonのバージョンによって標準ライブラリで提供されている関数の仕様が異なるので注意。標準ライブラリにない場合の実装例も本記事で示す。

  • Python3.4以前
    • 最大公約数: fractions.gcd()(引数は2つのみ)
  • Python3.5以降
    • 最大公約数: math.gcd()(引数は2つのみ)
  • Python3.9以降
    • 最大公約数: math.gcd()(3つ以上の引数をサポート)
    • 最小公倍数: math.lcm()(3つ以上の引数をサポート)

AtCoder(Python3.11.4)においては、math.gcd()およびmath.lcm()を3つ以上の引数で使用可能。

NumPyを使う方法は以下の記事を参照。NumPyの場合、複数の配列の要素ごとの最大公約数・最小公倍数の算出が簡単にできる。

本記事のサンプルコードではmathモジュールをインポートして使っている。

import math
source: gcd_lcm.py

2つの整数の最大公約数

Python3.5以降: math.gcd()

Python3.5以降はmathモジュールにgcd()関数がある。gcdは「greatest common divisor」の頭文字。

引数に指定した整数の最大公約数を返す。

print(math.gcd(6, 4))
# 2
source: gcd_lcm.py

Python3.4以前: fractions.gcd()

Python3.4以前ではmathモジュールではなくfractionsモジュールにgcd()関数があるので注意。fractionsをインポートして、fractions.gcd()とする必要がある。

2つの整数の最小公倍数

Python3.9以降: math.lcm()

Python3.9でmathモジュールに最小公倍数を返すlcm()関数が追加された。lcmは「least common multiple」の頭文字。

引数に指定した整数の最小公倍数を返す。

print(math.lcm(6, 4))
# 12
source: gcd_lcm.py

Python3.8以前: 最大公約数から算出

Python3.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
source: gcd_lcm.py

/を使うと結果が浮動小数点数floatになるため、小数点以下を切り捨て整数の除算結果を返す//(整数除算)を使っている。引数が整数かどうかなどの判定は行っていないので注意。

3つ以上の整数の最大公約数・最小公倍数

Python3.9以降: math.gcd(), math.lcm()

Python3.9からmath.gcd()math.lcm()も3つ以上の引数をサポートするようになった。

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

Python3.8以前: functools.reduce()を利用

Python3.8以前のmath.gcd()関数は2つの引数のみをサポートしている。

3つ以上の整数の最大公約数・最小公倍数を求める場合は、特に複雑なアルゴリズムは必要なく、順番に累積的に演算していけばよい。

gcd(a, b, c, d, ...) = gcd( ... gcd(gcd(gcd(a, b), c), d), ...)
lcm(a, b, c, d, ...) = lcm( ... lcm(lcm(lcm(a, b), c), d), ...)

これは標準ライブラリfunctoolsモジュールのreduce()で実現できる。

最大公約数

import functools

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

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

最小公倍数

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

def my_lcm(*integers):
    return functools.reduce(my_lcm_base, integers)

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

引数なしの場合の対応

引数なしの場合、math.gcd()0math.lcm()1を返す。

print(math.gcd())
# 0

print(math.lcm())
# 1

上で定義した関数は引数なしだとエラーになる。

# print(my_gcd())
# TypeError: reduce() of empty iterable with no initial value

# print(my_lcm())
# TypeError: reduce() of empty iterable with no initial value

引数なしに対応するには、reduce()の第3引数initializerを指定する。引数ありの場合の結果は変わらない。

def my_gcd_init(*integers):
    return functools.reduce(math.gcd, integers, 0)

print(my_gcd_init())
# 0

print(my_gcd_init(27, 18, 9, 3))
# 3
def my_lcm_init(*integers):
    return functools.reduce(my_lcm_base, integers, 1)

print(my_lcm_init())
# 1

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

関連カテゴリー

関連記事