N個の最大公約数の求め方 - To be Data Scientist

N個の最大公約数を求める

$x_1,x_2,\cdots,x_N$ の最大公約数を求めるにはユークリッド互除法を用いる.

ユークリッド互除法
$\mathrm{gcd}(a,b) \begin{cases} \mathrm{gcd}(~b~,a\mod b) & (b> 0) \\ a & (b=0) \end{cases}$

また,以下が成り立つ.

$\mathrm{gcd}(a,b,c)=\mathrm{gcd}(\mathrm{gcd}(a,b),c)$

これより,
$\mathrm{gcd}(x_1,x_2,\cdots,x_N)=\mathrm{gcd}(\mathrm{gcd}(x_1,x_2),\cdots,x_N)=\cdots$
を繰り返して行くことで最大公約数を求めることができる.

pythonでプログラムを書くと以下のようになる.(標準入力としてN個の値が与えられるとする)

#標準入力の読み込み
x_str=input().split()
x=list(map(int, x_str))
n=len(x)

#ユークリッド互除法の関数の定義
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)


if n==1:
    print(x[0])
else:
    element = gcd(x[0], x[1])
    if n==2:print(element)
    else:
        for i in range(2,n):
            element=gcd(element,x[i])
        print(element)