pythonによる最大公約数と最小公倍数の求め方

pythonを使った最大公約数と最小公倍数の求め方をまとめます。

目次

• 最大公約数とは
• 再帰関数を使って最大公約数をもとめる
• 最小公倍数とは
• 最小公倍数を利用して、最大公約数を求める

最大公約数とは

その名の通り、比較する各々の数値の共通する最大の約数のことです。

比較する数値が12,36として、それぞれの約数を上げると、

12 = {1,2,3,4,6,12}

36 = {1,2,3,4,6,9,12,36}

共通する最大の約数は12なので、最大公約数は12になります。

再帰関数を使って最大公約数をもとめる

再帰関数とユーグリットの互徐法を使って最大公約数を求めてみます。

ユーグリットの互徐法とは、
x >= yのときgcd(x,y)とgcd(y,xをyで割ったあまり)は等しいというものです。
詳しい証明などは別記事でまとめています。

この定理と再帰関数を使うと以下のように書くことができます。

def gcd(x,y):
    return gcd(y,x % y) if y > 0 else x

最小公倍数とは

最小公倍数とは、各々の数値の共通する最小の倍数を意味します。

12,36を例に上げると36ということになります。

最小公倍数を利用して、最大公約数を求める

最小公倍数は最大公約数を利用すると簡単に求めることができます。

比較する数値をa,bとすると、aとbを乗算したものをaとbの最大公約数で割ることで求めることができます。

これをpythonのコードにすると以下のようになります。

def lcm(a, b):
    return ((a*b) // gcd(a,b))