さて今日は最大公約数の問題でユークリッドの互助法にぶち当たりました。
ユークリッドの互助法とは...
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
最大公約数の書き方を覚えていればこっちは楽勝ですね。