Pythonで最小公倍数（LCM）を求める方法をわかりやすく解説

最小公倍数（LCM）とは

2つ（またはそれ以上）の数の最小公倍数（LCM：Least Common Multiple）とは、それらすべての数で割り切れる最も小さい数のことです。例えば、12と20の場合、両方の数で割り切れる最小の数は60となります。

基本的な求め方

シンプルなアルゴリズムは以下の手順で構成されます。

まず、与えられた2つの数のうち大きい方を取得します。その値から順に1ずつ増やしながら、両方の数で割り切れる最初の数を探します。見つかった数が最小公倍数（LCM）です。

サンプルコード

x=12
y=20
if x > y:
    greater = x
else:
    greater = y
while(True):
    if((greater % x == 0) and (greater % y == 0)):
        lcm = greater
        break
    greater += 1

print ("LCM of {} and {}={}".format(x,y,lcm))

実行結果

出力は以下のようになります。

LCM of 12 and 20=60

より効率的な方法：GCDを利用する

扱う数が大きい場合、上記の方法ではループ回数が増えて計算に時間がかかることがあります。そんなときは、最大公約数（GCD）を利用すると効率的です。2つの数 a と b の最小公倍数は、次の公式で求められます。

LCM = a × b ÷ GCD(a, b)

GCDを使ったサンプルコード

import math

x = 12
y = 20
lcm = (x * y) // math.gcd(x, y)
print("LCM of {} and {}={}".format(x, y, lcm))

この方法なら、ループ処理を一切行わずに瞬時に最小公倍数を計算できるため、実務でも推奨されるアプローチです。