［解決！Python］ユークリッドの互除法で最大公約数を求めるには：解決！Python

2つの自然数の最大公約数を求めるために使われるユークリッドの互除法の説明と、それに基づいて最大公約数を求める関数の実装を幾つか紹介する。

[かわさきしんじ，Deep Insider編集部]

連載目次

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

# 再帰を使った書き方
def gcd_recursive(a, b):
    if b == 0:
        return a
    elif a == 0:
        return b

    return gcd_recursive(b, a % b)

# ユークリッドの互除法を愚直にコードにしたもの
def gcd0(a, b):
    if a < b:
        a, b = b, a
    
    if b == 0:
        return a
    
    r = a % b

    while r != 0:
        a, b = b, r
        r = a % b

    return b

r0, r1, r2 = gcd(10, 25), gcd0(10, 25), gcd_recursive(10, 25)
print(r0, r1, r2)  # 5 5 5

r0, r1, r2 = gcd(66, 24), gcd0(66, 24), gcd_recursive(66, 24)
print(r0, r1, r2)  # 6 6 6

r0, r1, r2 = gcd(10, 0), gcd0(10, 0), gcd_recursive(10, 0)
print(r0, r1, r2)  # 10 10 10

r0, r1, r2 = gcd(56, 98), gcd0(56, 98), gcd_recursive(56, 98)
print(r0, r1, r2)  # 14 14 14

r0, r1, r2 = gcd(7, 1), gcd0(7, 1), gcd_recursive(7, 1)
print(r0, r1, r2)  # 1 1 1

ユークリッドの互除法とは

　2つの自然数aとbがあったとき、両者を割り切れる自然数のことを公約数といい、その中で最大の値を最大公約数（GCD：Greatest Common Divisor）という（ここでは自然数に0を含めることにする）。手作業やプログラムで2つの自然数の最大公約数を求めるのによく使われるのが「ユークリッドの互除法」と呼ばれるアルゴリズムだ。

　ユークリッドの互除法での最大公約数の求め方を以下にまとめる。

1. 2つの自然数aとbがあったとする（ここではa＞bとする）
2. aをbで割った余りrを求める。このとき、2つの数の関係はa＝b×q＋rと表現できる（qの値は知らなくても問題ない）
3. 余りrが0であれば、直前の割り算における除数（b）が最大公約数である
4. 余りrが0でなければ、bをrで割って新たに余りrの値を求める
5. 余りが0になるまで3と4を続ける

　なぜこの考え方で最大公約数を求められるのだろう。

　2つの自然数aとbがあり、aをbで割ったとき、その関係は上でも述べたように「a＝b×q＋r」と表現できる。この式を変形すると「r＝a−b×q」となることも覚えておこう。

　ここでaとbの両者を割り切れる最大の自然数d₀について考えてみる（d₀はaとbの最大公約数）。上で示した式「r＝a−b×q」に注目すると、d₀がaとbを割り切れるのでこの式は「r＝a₀×d₀−b₀×q×d₀＝d₀×（a₀−b₀×q）」とも表現できる（a₀とb₀はaとbとは異なる値かもしれないことを意味している）。つまり、余りrもまたd₀で割り切れる（d₀はbとrの公約数でもある）。

　同様に、bとrを割り切れる最大の自然数d₁について考えてみる（d₁はbとrの最大公約数）。すると、「a＝b×q＋r」という式は「a＝b₁×q×d₁＋r₁×d₁＝d₁×（b₁×q＋r₁）」であり、d₁はaとbの公約数でもある。

　d₀はaとbの最大公約数であり、d₁もaとbの公約数であることを考えると、d₁はd₀以下の値となる（d₁≦d₀。なぜならd₀がaとbの「最大公約数」だから）。一方、d₁はbとrの最大公約数であり、d₀もbとrの公約数であることを考えると、d₀はd₁以下の値となる（d₀≦d₁。なぜならd₁がbとrの「最大公約数」だから）。この2つの条件を満たすのだから「d₀＝d₁」となる。

　なお、余りrが0になった時点で、最初の式「a＝b×q＋r」は「a＝b×q」となり、このときのbの値が最大公約数となる。また、2つの数aとbのどちらかが0であれば、それらの最大公約数はもう一方の数となる（両者を割り切れる最大の数は0ではない方になる）。

　ここでd₀=GCD(a, b)、d₁＝GCD(b, r)と置くと、GCD(a, b)＝GCD(b, r)である。これは最大公約数を求めるには剰余が0になるまで両者の整数除算を続ければよいことを意味している。

　このことを愚直にコードにしたのが以下だ。

def gcd0(a, b):
    if a < b:  # a > bとなるように調整する
        a, b = b, a
    
    if b == 0:  # bが0なら最大公約数はもう一方
        return a
    
    r = a % b

    while r != 0:  # 余りが0になるまで整数除算を繰り返す
        a, b = b, r
        r = a % b

    return b  # 余りが0になった時点でのbの値が最大公約数

　だが、上のコードはよりシンプルに次のように書ける。

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

　gcd0関数の冒頭ではa＞bとなるようにしているが、gcd関数ではそうしたチェックをしていないのは、a＜bであっても、while文にある「a, b = b, a % b」行によりa＞bとなるような代入が行われるからだ。また、gcd0関数ではb（小さい方の値）が0ならもう一方を戻り値とするコードもあるが、gcd関数ではこれも省略されている。呼び出し時点でbの値が0ならwhile文の実行がキャンセルされaの値が返されるからだ。

　また「GCD(a, b)＝GCD(b, r)」であることから、再帰を使って次のようにも書けるだろう。

def gcd_recursive(a, b):
    if b == 0:  # 余りが0、または一方が0ならもう一方が最大公約数
        return a
    if a == 0:  # 一方が0ならもう一方が最大公約数
        return b

    return gcd_recursive(b, a % b)  # GCD(b, r)を返す

　これらの関数は0と0の最大公約数として0を返すようになっている。これが許されない場合、関数冒頭に以下のようなコードを含めるのがよいだろう。

def gcd(a, b):
    if a == b == 0:
        raise ValueError('gcd(0, 0) is not defined.')

    while b != 0:
        a, b = b, a % b
    return a

　最後に最大公約数を求める例を示す。

r0, r1, r2 = gcd(10, 25), gcd0(10, 25), gcd_recursive(10, 25)
print(r0, r1, r2)  # 5 5 5

r0, r1, r2 = gcd(66, 24), gcd0(66, 24), gcd_recursive(66, 24)
print(r0, r1, r2)  # 6 6 6

r0, r1, r2 = gcd(10, 0), gcd0(10, 0), gcd_recursive(10, 0)
print(r0, r1, r2)  # 10 10 10

r0, r1, r2 = gcd(56, 98), gcd0(56, 98), gcd_recursive(56, 98)
print(r0, r1, r2)  # 14 14 14

r0, r1, r2 = gcd(7, 1), gcd0(7, 1), gcd_recursive(7, 1)
print(r0, r1, r2)  # 1 1 1

「解決！Python」

AI・データサイエンスの学びをここから

初心者向け、データ分析・AI・機械学習・Pythonの勉強方法　＠ITのDeep Insiderで学ぼう