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

5618번: 공약수

문제

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

 

입력

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

 

출력

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

 

코드

import math

# 최대공약수 구하기 (유클리드 호제법)
def gcd(a, b):
    if b > a:
        a, b = b, a
    if a % b == 0:
        return b
    return gcd(b, a % b)

# 약수 구하기
def get_divisor(num):
    res = []
    # 일단 num의 제곱근까지만 약수 구하기
    for i in range(1, int(math.sqrt(num)) + 1):  
        if num % i == 0:
           res.append(i) 
    # 제곱근까지만 구한 약수들 가지고 num을 나눠서 나머지 약수 구하기
    l = len(res)
    for i in range(l):
        res.append(num // res[i])
    return sorted(set(res))

n = int(input())
nums = list(map(int, input().split()))

if n == 2:
   for i in get_divisor(gcd(nums[0], nums[1])):
       print(i)
else:
    for i in get_divisor(gcd(nums[0], gcd(nums[1], nums[2]))):
        print(i)

두 수의 최대공약수를 구하여 그 수의 약수를 구하는 방법으로 풀이하였다.

두 수의 최대공약수는 유클리드 호제법을 이용하여 구하였다.

그리고 그 수에 대해 효율적으로 약수 구하는 방법을 사용하여 약수들을 구해주었다.

 

 

• 유클리드 호제법이란?

유클리드 호제법 (최대공약수 구하는 알고리즘)

 

• 효율적으로 약수 구하기

효율적으로 약수 구하기