最大公約数

2022-09-25 · algorithms, python

Pythonで再帰を用いて効率的に最大公約数を求める関数を実装してみます。
元となるコードは『アルゴリズムサイエンス：入口からの超入門』（著：浅野哲夫）のP.73より引用しました。
今回のコードでは、ユークリッドの互除法を用いて O(log n) の回数で最大公約数を求めます。

以下のコードで、m と n の2つの自然数の最大公約数を求めることができます。
もし n == 0 の場合、 m が最大公約数となるため、そのまま m を返します。
n != 0 の場合、m を n で割った余りを求め、再帰的に gcd 関数を呼び出します。

def gcd(m, n):
    if n == 0:
        return m
    return gcd(n, m % n)

m と n の最大公約数は、m を n で割った余り m % n と n の最大公約数と等しいため、このコードが成り立ちます。
この法則を ユークリッドの互除法 といいます。

古代ギリシャでは広く知られていたアルゴリズムですが、紀元前300年頃にユークリッドが著書『原論』にまとめたことで、彼の名が付けられました。
『原論』第7巻の命題1から3に記されています。
これは、明示的に記述された最古のアルゴリズムの一つとされています。