007: G.C.D

ヒント / 解答

難易度: ☆

問題

関数 gcd(a, b) を書いてください。 この関数は、2つの非負整数 a と b の最大公約数を返します。

最大公約数は、2つの整数をどちらも割り切る正の整数のうち、最大のものです。 たとえば、48と18の最大公約数は6です。

この問題では、Euclidの互除法を使ってください。 math.gcd は使わないでください。

制約

• a と b は整数です。
• a と b は0以上です。
• a と b が同時に0になる入力は扱いません。
• math.gcd は使いません。

例

>>> gcd(48, 18)
6
>>> gcd(1071, 462)
21
>>> gcd(0, 5)
5
>>> gcd(17, 13)
1

確認

RSA暗号では、2つの数が互いに素かを判定します。 互いに素とは、最大公約数が1であることです。

>>> gcd(17, 3120)
1
>>> gcd(18, 3120)
6