paiza ユークリッドの互除法メニュー ユークリッドの互除法Python解説

2021年12月31日

ユークリッドの互除法

2 つの整数 A , B の最大公約数（以後 gcd(A , B)）を高速に求めるアルゴリズムとして、ユークリッドの互除法があります。
gcd(A, B) をユークリッドの互除法で求める手順は次の通りです。

1.A , B のうち、いずれかが 0 の場合 手順 3 に進む
2.A , B のうち小さい方で大きい方をわり、大きい方をその余りで置き換え、手順 1 に戻る
3.このとき、0 でない方の数が求めたい最大公約数になっている。

A , B の最大公約数の値を 1 行で出力してください。

paiza「ユークリッドの互除法」

ユークリッドの互除法を行う関数を作っていきます。因みにユークリッドの互除法では関数名にgcdが使われますが、これはGreatest Common Divisorの略であり、最大公約数の英語です。

a, b = map(int, input().split())

def gcd(a, b):
    if b == 0:
        return a 
    return gcd(b, a % b)
    
print(gcd(a, b))

ユークリッドの互除法をPythonで実装すると上記のコードになります。bが0になったらそのときのaの値を返し、bが0になっていなければ0になるまで再帰を行っています。

また、手順2の大小判定ですが、大きい数値で小さい数値を割った場合、両方の数値が入れ替わるだけなので、上記のコードの場合、A,Bの大小判定は行わなくて大丈夫です。