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

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 5618번 공약수
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

주어진 수들의 공약수를 오름차순으로 모두 출력하는 문제입니다.

코드

input()
l=list(map(int,input().split()))

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

t=gcd(gcd(l[0],l[1]),gcd(l[1],l[-1]))
r=[]
for i in range(1,int(t**0.5)+1):
    if t%i==0: r.append(i)
s=len(r)
for i in range(1,s+1):
    p=t//r[s-i]
    if p*p!=t:r.append(p)
print('\n'.join(map(str,r)))

설명

먼저 최대공약수 t를 구하고, t의 약수를 제곱근까지 탐색해 짝 약수까지 함께 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---