ユークリッドの互除法による最大公約数の求め方

概要

ユークリッドの互除法とは、２つの自然数の最大公約数(Gratest Common Divisor)を求める手法の一つです。一方をもう一方で割って剰余を求め、その剰余を使ってさらに除算を繰り返すことで、最終的に剰余が0になった時点で最大公約数を見つけることができます。最古のアルゴリズムとしても知られ、紀元前300年頃に編纂されたユークリッドの『原論』にその記述があります。

実装例

def gcd(a, b):
    # 大きい方を被除数、小さい方を除数とする
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    # 最大公約数を見つけるまで繰り返す
    while dividend % divider != 0:
        # 除算を行い、その除数を次回の被除数、剰余を次回の除数として処理を繰り返す
        r = dividend % divider
        dividend = divider
        divider = r
    
    # 一方がもう一方を割り切れた時点で、その除数を最大公約数とみなせる
    return divider

注意点

厳密には被除数と除数の大小関係は関係ない（被除数の方が小さい場合、被除数がそのまま剰余となり、次回の処理で除数と入れ替わる）のですが、本記事では直感的にわかりやすくするため最初の除算で大きい方を小さい方で割るようにしています。

参考

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_B
https://ja.wikipedia.org/wiki/ユークリッドの互除法