5618 공약수

문제

자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 2 또는 3이다. 둘째 줄에는 공약수를 구해야 하는 자연수 n개가 주어진다. 모든 자연수는 108 이하이다.

출력

입력으로 주어진 n개 수의 공약수를 한 줄에 하나씩 증가하는 순서대로 출력한다.

 

 

 

 

공약수를 구하는 문제.

 

막히는 부분이 많아 참고를 했다.

출처:https://pacific-ocean.tistory.com/177

 

공약수는 최대공약수의 약수이다. 그리고 최대공약수는 GCD로 유클리드 호제법을 이용하는게 빨랐다.

 

유클리드 호제법이란

a,b의  최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다는 법칙이다.

이 때 b를 a로, 나머지를 b로 옮기고 b가 0이 될때까지 실행하면 남은 a가 최대공약수가 된다.

 

그렇게 최대공약수를 구하고, 약수는 절반까지 구하면 되므로

최대공약수의 절반까지의 범위에서 약수를 출력한다.

 

 

변수 : n

order ( 공약수 찾을 숫자 저장)

g= 최대공약수

 

 

import sys
input=sys.stdin.readline
def gcd(a,b):
    while b>0:
        a,b=b,a%b
    return a
n=int(input())
order=list(map(int,input().split()))
g=  gcd( order[0] ,  gcd(order[1],order[-1])  )

for i in range(1,(g//2)+1):
    if g%i==0:
        print(i)
print(g)