ユークリッドの互除法

ユークリッドの互除法

ユークリッドの互除法 は２つの自然数の 最大公約数 を効率的に求めることができるアルゴリズムです。

ユークリッドの互除法 は、次の定理に基づいており、その名の通り除法つまり 割り算 を繰り返して計算しています。

[定理]

２つの自然数 a, b について、a を b で割ったときの商 q、余りを r とすると、
a と b の最大公約数 は b と r の最大公約数 に等しい。

例として、a=1274、b=975 の場合、次のように 最大公約数 を求めることができます。

(1) 1274 ÷ 975 = 1 余り 299
(2) 975 ÷ 299 = 3 余り 78
(3) 299 ÷ 78 = 3 余り 65
(4) 78 ÷ 65 = 1 余り 13
(5) 65 ÷ 13 = 5 余り 0

ソースコード

上記の例をコードにすると下記のようになります。

[Google Colaboratory]

# ユークリッドの互除法
def gcd(a, b):
    while b != 0:         # 余りが0になるまで繰り返す
        a, b = b, a % b   # [割る数]と[割られる数]を入れ替え、[余り]を[割る数]に代入
    return a              # 最大公約数を返す(余りが0になったときの[割る数])

print(gcd(1274, 975))

[実行結果]

13

効率的に 最大公約数 を求めることができました。