[알고리즘]백준 5618번: 공약수

알고리즘 유형: 수학, 브루트 포스 

문제

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

입력

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

출력

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

 

풀이

---

일단 최대 공약수를 계산해주겠습니다 

 

두 수 a,b의 최대 공약수는 작은 수 min(a,b)를 넘어 가지 않으며 a와 b를 나누었을때 나누어떨어지는 수입니다 

range를 통해 min(a,b)부터 1까지 스캔해주면서 나누어지면 반복문을 탈출하고 이때의 숫자를 return 합니다 

 

숫자의 갯수는 최소 2 최대 3입니다. 조건문을 통해 각각의 경우를 나누어줍니다. 

 

 

import sys 
import math 
N = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip(" ").split()))

def gcd(a,b): #math.gcd로 대체가능 
    for i in range(min(a,b),0, -1):
        if a % i == 0 and b % i == 0:
            return i 
if N==2: 
    gcd_ =gcd(nums[0], nums[1])
else: 
    gcd_ = gcd(gcd(nums[0], nums[1]), nums[2]) 
answer =set()
for i in range(1, int(gcd_**0.5)+1):
    if gcd_%i == 0:
        answer.add(i)
        answer.add(gcd_//i)
answer =sorted(answer)
print(*answer, sep="\n")