Skip to content

ユークリッドの互除法

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

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

関連

参考