[백준 Python] 5618번 공약수

백준 5618 공약수

문제

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

입력

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

출력

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

풀이 및 회고

풀이

최대공약수를 gcd를 이용하여 구한 다음 그에 대한 약수들을 구하면 된다.

회고

브론즈 3이라 그런지 너무 쉽게 보고 문제에 접근한 것 같다. 거기다가 설이라 노트북으로 하고 있는데 설정을 안해놔서 애먹기도 했다. 심지어 약수 구하는 알고리즘이 떠오르지 않아 참고하기도 했다.(참고한 티스토리 글..) 내일은 좀 집중해서 풀어야지..

코드

from math import gcd, sqrt

def div(n: int) -> list:

    tmp = []
    for i in range(1, int(sqrt(n)) + 1):
        if (n % i == 0):
            tmp.append(i) 
            if ( (i**2) != n) : 
                tmp.append(n // i)
    tmp.sort()
    return tmp

n = int(input())
if n == 2:
    a, b = map(int, input().split())
    ls = div(gcd(a, b))
    for element in ls:
        print(element)
else:
    a, b, c = map(int, input().split())
    ls = div(gcd(a, gcd(b, c)))
    for element in ls:
        print(element)

>> iwtkmn0219의 Github <<