＜アルゴリズムの基本⑩＞ 繰り返し処理（８） ユークリッドの互除法

今回は、ユークリッドの互除法を使った２つの数値の最大公約数を求めるアルゴリズムについてまとめます。

ユークリッドの互除法について

まずはユークリッドの互除法について、おさらいです。

ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。ウィキペディア:ユークリッドの互除法より

擬似コード例

擬似コード例を以下に示します。

Procedure GCD(A, B)
    R ← A÷Bの剰余
    while R is not 0 do # 余りが0になるまで繰り返す
          A ← B
          B ← R
          R ← A÷Bの剰余
    end-while
    return B

Pythonコード例

Pythonのコード例を以下に示します。繰り返し処理を使った場合と、再帰処理を使った場合それぞれ記載しました。（コードはこちらにアップロードしてあります）

# 繰り返し処理版
>>> def iterative_gcd(a, b):
...     r = a % b
...     while(r != 0):
...         a = b
...         b = r
...         r = a % b
...     return b

# 再帰処理版
>>> def recursive_gcd(a, b):
...     r = a % b
...     if r == 0:
...         return b
...     else:
...         return recursive_gcd(b, a % b)

実行結果

# 繰り返し処理版
>>> iterative_gcd(24, 36)
12

# 再帰処理版
>>> recursive_gcd(24, 36)
12

まとめ

今回はユークリッド互除法を用いた最大公約数の求め方についてのアルゴリズムについてまとめました。繰り返し処理を使った基本的なアルゴリズムについては一旦ここまでにして、次回からは並べ替え（ソート）アルゴリズムについてまとめる予定です。