ユークリッドの互除法

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

ユークリッドの互除法とは以下の最大公約数の性質を利用して、2つの整数m, nの最大公約数を求めるアルゴリズム。

最大公約数の性質

\(m\)を\(n\)で割ったときの余りを\(r\)としたとき、

\(GCD(m, n) = GCD(n, r)\)
\(\scriptsize 最大公約数 \; GCD: greatest \; common \; divisor\)

が成り立つ

この性質を利用して下記のようにして最大公約数を求める手続きのことをユークリッドの互除法と呼ぶ。

1. \(m\)を\(n\)で割ったときの余りを\(r\)とする。
2. \(r=0\)であれば、\(n\)が求める最大公約数。
3. \(r \neq 0\)の場合には\(m \leftarrow n, n \leftarrow r\)として手順1に戻る。

計算量は\(m \geq n > 0\)としたとき、\(O(\log n)\)になる。

実装例

再帰関数を用いることで簡潔に実装できる。

# ユークリッドの互除法
def GCD(m, n):
    if n == 0:
        return m
    
    return GCD(n, m % n)

if __name__ == "__main__":
    print(GCD(55, 10)) # -> 5
    print(GCD(27, 18)) # -> 9
    print(GCD(1020, 120)) # -> 60

補足

Pythonでは標準ライブラリのmathモジュールにあるgcdを利用できる。

>>> from math import gcd
>>> gcd(5, 10, 15, 20)
5
>>> gcd(3785, 5176, 10740, 7744, 3999, 3143, 9028, 2822,4748, 6888)
1
>>> gcd(-1391, -5564, 2996, 3745, 856, -5885, 6206, -1926, -2140)   
107