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

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

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

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

AtCoderにおいては、2021年1月2日時点でPythonのバージョンが3.8.2なので、math.gcd()関数を使用可能。ただし、引数は2つのみ。今後さらにアップデートされる可能性もあるので、言語選択で表示されるPythonのバージョンを要確認。

• 関連記事: AtCoderのPython, NumPy, SciPyのバージョンと注意点（2020年5月）

ここではPythonの標準ライブラリによる方法を説明する。NumPyを使う方法は以下の記事を参照。NumPyの場合、複数の配列の要素ごとの最大公約数・最小公倍数の算出が簡単にできる。

• 関連記事: NumPyで最大公約数・最小公倍数を算出・取得

2つの整数の最大公約数・最小公倍数

最大公約数

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

• math.gcd() --- 数学関数 — Python 3.9.1 ドキュメント

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

import math

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

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

• fractions.gcd() --- 有理数 — Python 3.7.3 ドキュメント

最小公倍数

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

• math.lcm() --- 数学関数 — Python 3.9.1 ドキュメント

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

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

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

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

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

Python3.9以降

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

リストの要素の最大公約数・最小公倍数を算出したい場合は*を付けて引数に指定する。

• 関連記事: Pythonで関数の引数にリスト、タプル、辞書を展開して渡す

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

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

Python3.8以前

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

3つ以上の複数の整数の最大公約数・最小公倍数を求める場合、特に複雑なアルゴリズムは必要なく、2つずつ演算していけばOK。高階関数reduce()を使って複数の値に対して順番に最大公約数・最小公倍数を計算すればよい。

• functools --- 高階関数と呼び出し可能オブジェクトの操作 — Python 3.9.1 ドキュメント

最大公約数

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

繰り返しになるが、Python3.4以前はmathモジュールではなくfractionモジュールに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