paiza ユークリッドの互除法メニュー 3つ以上の整数の最大公約数Python解説

スポンサーリンク

3つ以上の整数の最大公約数

2 つの整数 A , B の最大公約数(以後 gcd(A , B))を高速に求めるアルゴリズムとして、ユークリッドの互除法があります。
gcd の演算では、3 つの整数 a, b, c の最大公約数は、gcd(gcd(a,b),c) で求めることができます。
これは 4 つ以上の整数の場合も同様に、a , b , c , d , e , … の最大公約数は
gcd(…gcd(gcd(gcd(gcd(a,b),c),d),e)…) で求めることができます。
例として、(9,27,33) の最大公約数は gcd(gcd(9,27),33) = gcd(9,33) = 3 といった具合に求めることができます。
与えられる整数の数 N と、整数 A_1, …, A_N が与えられるので、 A_1, …, A_N の最大公約数を求めてください。

paiza「3つ以上の整数の最大公約数」

3つ以上の整数の最大公約数を求める問題です。まず、ユークリッドの互除法を関数で定義し、for文で1組ずつ最大公約数を調べていきます。

n = int(input())
a = [int(input()) for _ in range(n)]

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

g = a[0]

for i in range(1, n):
    g = gcd(g, a[i])
    
print(g)

ユークリッドの互除法は2つの数値が必要なため、g = a[0]で配列の先頭の数値を抜いています。
そして、g = gcd(g, a[i])とすることで、最大公約数の戻り値がgに入ります。これを整数の数nまでループさせて完了です。