paiza ユークリッドの互除法メニュー ユークリッドの互除法Python解説
ユークリッドの互除法
2 つの整数 A , B の最大公約数(以後 gcd(A , B))を高速に求めるアルゴリズムとして、ユークリッドの互除法があります。
paiza「ユークリッドの互除法」
gcd(A, B) をユークリッドの互除法で求める手順は次の通りです。
1.A , B のうち、いずれかが 0 の場合 手順 3 に進む
2.A , B のうち小さい方で大きい方をわり、大きい方をその余りで置き換え、手順 1 に戻る
3.このとき、0 でない方の数が求めたい最大公約数になっている。
A , B の最大公約数の値を 1 行で出力してください。
ユークリッドの互除法を行う関数を作っていきます。因みにユークリッドの互除法では関数名に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の大小判定は行わなくて大丈夫です。