GCD - Euclid’s algorithm

アルゴリズムを数回反復すると、いくつかの重複した処理があることに気づき、実は最大公約数 (GCD) を求めるアルゴリズムはさらに最適化できることがわかります。

減算を使う方法では、大きい数から小さい数を引き続けて、結果が 0 または GCD と等しい数になるまで処理を進めます。これをより効率的に行うために、大きい数を小さい数で割った余りを使います。つまり、割り算の余り (modulo) を求めながら、大きい数を小さい数で何度も割っていき、余りが 0 になるまで繰り返します。最後に得られる 0 でない余りが GCD になります。

modulo 演算を使うやり方は、GCD を求めるうえでより効率的だと考えてください。小さい数を大きい数から繰り返し減算する代わりに、割り算を用いて大きい数を一気に小さくできます。両方の数を共通の約数で徐々に割っていくイメージなので、最大公約数にずっと早く到達します。

a, b = int(input()), int(input())
while a > 0 and b > 0:  # aまたはbが0の場合 ⇒ もう一方がGCD
    a, b = b, a % b     # (a, b) のgcdは (b, a % b) のgcdと同じ

d = b if a == 0 else a  # aが0ならbがGCD、bが0ならaがGCD
print('gcd:', d)

このアルゴリズムは、紀元前 300 年に書かれたユークリッドの著書で最初に言及されています。

いくつかアルゴリズムのシミュレーションを見てみましょう:

入力

The only line of the input contains two integers a and b (0 ≤ a, b ≤ ).

出力

The program should print the greatest common divisor of a and b.

例