[python/파이썬] 백준 5618 공약수

문제

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

입력

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

출력

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

예제 입력 1 복사

2
75 125

예제 출력 1 복사

1
5
25

예제 입력 2 복사

3
110 22 88

예제 출력 2 복사

1
2
11
22

예제 입력 3 복사

3
66 11 3

예제 출력 3 복사

1

 

 

[나의 접근 방법]

머리가 잘 안돌아가길래 조금 쉬운걸로 풀어보자 하고 고른 문제였는데 생각보다 간단하지는 않았다.

두 수 혹은 세 수의 공약수들을 구하는 문제였는데 문제 자체는 간단하나, n이 2혹은 3이라는 것에서 조금 헤맸다.

노가다로 경우를 나누어 풀어보려고 했으나 너무 바보같은 방법이라 포기하고 다른 방법으로 해결하였다.

 

[소스 코드]

gcd는 최대공약수를 뜻한다.

공약수는 최대공약수의 약수이기 때문에 우선 최대 공약수를 구하는 것 먼저 한다.

g가 구해진 최대 공약수이다.

gcd 함수는 2개의 인자를 갖고 있지만, gcd를 재귀적으로 호출하면 n이 3인경우도 문제없다.

최대공약수를 구한 다음에는 최대공약수의 약수를 구하기 위해 for문에서 %연산을 통해 완전히 나눠지는 경우만 출력하도록 한다.

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

n=int(input())
data = list(map(int,input().split()))
g = gcd(data[0], gcd(data[1],data[-1]))

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