さて今日は最大公約数の問題でユークリッドの互助法にぶち当たりました。

ユークリッドの互助法とは...

2つの自然数 𝑎, 𝑏 について，𝑎 を 𝑏 で割ったときの商を 𝑞，余りを 𝑟 とすると
「𝑎 と 𝑏 の最大公約数」は，「𝑏 と 𝑟 の最大公約数」に等しい。

具体例で表すと

120 ÷ 50 = 2 ... 20
50　÷ 20 = 2 ... 10
20　÷ 10 = 2 ... 0
(10　÷ 0 = 10を返す)

この場合10が最大公約数となります。

def gcd(x, y):
    if y == 0: #上記の数式だと10÷0=の場合、10を返す。つまり余りが0で計算が終わりの場合
        return x
    else: #あまりの数でわる式を返す
        return gcd(y,x%y)

print(gcd(12, 18))

次に最大公倍数。これは最大公約数がわかっていたら簡単なんですね。

aとbの最小公倍数は

最小公倍数　＝　a÷ 最大公約数　× b

という公式があるようで。何か見覚えがあるような気もする。

ということで最小公倍数は以下のように求められます。

def lcm(x, y):
	return int(x / gcd(x, y)) * y

最大公約数の書き方を覚えていればこっちは楽勝ですね。