このページではPythonで最小公倍数（lcm：least common multiple）を求める方法について解説します。
math.lcm（Python3.9以降）
Python3.9以降、標準ライブラリのmathにlcmという最小公倍数を求める関数が用意されています。引数に最大公約数を求める２数を指定します。
import math my_lcm = math.lcm(12, 39) print(my_lcm) # 156
ただし、Python3.9より前の古いPython3にはこの関数は実装されていないため、後述するロジックを使用してみてください。
3つ以上の数の最小公倍数を求める
引数に3つ以上の数を指定することも可能です。
import math my_lcm1 = math.lcm(12, 39, 42) print(my_lcm1) # 156 data = [12, 36, 39, 42] my_lcm2 = math.lcm(*data) print(my_lcm2) # 3276
最小公倍数を求めるアルゴリズム
Python3.9より古いバージョンを使用する場合や、理解を深めるため最大公約数算出を自力で実装してみたい、という方向けにアルゴリズムを紹介します。よく知られた方法として最大公約数を使用する方法があります。
2つの正の整数の積はその最小公倍数と最大公約数の積に等しくなります。つまり、
Prop
任意の正の整数a, bに対しa*b=lcm*gcdこの命題の式をlcmについて解くとlcm = (a*b)/gcd となります。以下コードはこの式実装例となります。なお、a*b/gcd を計算する際、gcdは必ず割り切れるため割り算を先に行うことで内部で扱う数の桁数を抑えることができます。
import math
def lcm(a, b):
return (a/ math.gcd(a, b)) * b
lcm(12, 39) # 156
最大公約数については以下を参照してください。
