[수학/유클리드 호제법] 백준 5618 공약수 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

5618번: 공약수

 

 

 

2. 문제 풀이

 자연수 n개가 주어질 때, 모든 공약수를 구하는 문제입니다.

 

2022.02.05 - [Algorithm] - [Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

[Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

 최대 공약수를 먼저 구하고, 최대 공약수의 약수를 구하면 모든 공약수를 구할 수 있습니다.

 

 

 

3. 코드

# 입력
n = int(input())
numlist = list(map(int, input().split()))

# 최소공약수 찾기
def find_gcd(a, b):
    if a < b:
        a, b = b, a

    while a != 0:
        b %= a
        a, b = b, a
    return b

gcd = numlist[0]  # 최대 공약수 찾기
for i in numlist:
    gcd = find_gcd(gcd, i)

# 약수 찾기
divisor = set()
for i in range(1, int(gcd**0.5)+1):
    if gcd % i == 0:
        divisor.add(i)
        divisor.add(gcd // i)

# 출력
for i in sorted(divisor):
    print(i)

 유클리드 호제법에 관한 설명과 코드는 위 링크에서 볼 수 있습니다.