【超入門】最大公約数の求め方と応用例！Pythonでの実装も紹介

そまちょブログのそまちょ（@somachob）です。

競技プログラミングにおいて、最大公約数はとても大切なものの一つです。

最大公約数を計算することで、複数の数の約分や最小公倍数の計算をすることができます。

この記事では、最大公約数の求め方と応用例について、Pythonを用いた実装も交えて解説してます。

最大公約数とは

最大公約数は、2つ以上の数の最も大きい共通の約数です。

例えば、12 と 18 の約数は次のようになります。

このうち、最も大きい約数は 6 なので、12 と 18 の最大公約数は 6 になります。

8 と 12 と 24 の最大公約数は、4 になります。

最大公約数の求め方

最大公約数を求める方法の１つであるユークリッドの互除法について説明します。

ユークリッドの互除法

ユークリッドの互除法は、2つの整数 a, bの最大公約数を求めるアルゴリズムです。

ユークリッドの互除法のアルゴリズムは次のようになります。

このアルゴリズムを、再帰関数を使って実装したのが、次のコードになります。

gcd は、Greatest Common Divisor の略になります。

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

再帰関数については、次の記事を参考にしてください。

再帰関数ではなく、while を使った実装だと次のようになります。

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

実際に、この関数を使って最大公約数を求めてみます。

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

print(gcd(12, 18))	# => 6

print(gcd(9, 6))	# => 3

3つ以上の最大公約数を求めたいときには、2つの数の最大公約数を求めて、その最大公約数と残った数の最大公約数を求めます。

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# 8と12の最大公約数を求めて、それと24の最大公約数を求める
print(gcd(gcd(8, 12), 24))	# => 4

math.gcd()

Pythonでは、mathモジュールで gcd 関数が提供されています。

自分で実装しなくても、math モジュールをインポートすることで最大公約数を求めることができます。

import math

print(math.gcd(12, 18))	# => 6

print(math.gcd(9, 6))	# => 3

最大公約数の応用例

最大公約数を使って、最小公倍数を求めることができます。

最小公倍数とは

最小公倍数は、２つ以上の数の最小の共通の倍数です。

例えば、12 と 18 の倍数は次のようになります。

このうち、最も小さい倍数は 36 なので、12 と 18 の最小公倍数は 36 になります。

最小公倍数の求め方

最小公倍数は、２つの数を掛けたものを最大公約数で割ることで求めることができます。

12 と 18 の最大公約数は 6 なので、最小公倍数は 12 × 18 ÷ 6 = 36 になります。

これを実装したのが次のコードになります。

lcm は、Least Common Multiple の略になります。

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
      
def lcm(a, b):
    return (a * b) // gcd(a, b)
  
print(lcm(12, 18))	# => 36

print(lcm(3, 4))	# => 12

まとめ

最大公約数は、ユークリッドの互除法を使って求めることができます。

最大公約数を使うことで最小公倍数を求めることもできます。