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の場合、複数の配列の要素ごとの最大公約数・最小公倍数の算出が簡単にできる。
- 関連記事: NumPyで最大公約数・最小公倍数を算出・取得
本記事のサンプルコードではmath
モジュールをインポートして使っている。
import math
2つの整数の最大公約数
Python3.5以降: math.gcd()
Python3.5以降はmath
モジュールにgcd()
関数がある。gcd
は「greatest common divisor」の頭文字。
引数に指定した整数の最大公約数を返す。
print(math.gcd(6, 4))
# 2
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
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
/
を使うと結果が浮動小数点数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()
は0
、math.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