[백준] 2609 최대공약수와 최소공배수

J. Hwang·2024년 12월 28일

Coding python 코딩테스트

coding test

목록 보기

67/108

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

내 풀이

a, b = map(int, input().split())

max1 = max(a, b)

eratosthenes = [False,False] + [True]*(max1-1)

primes=[]

for i in range(2,max1+1):
    if eratosthenes[i]:
        primes.append(i)
        for j in range(2*i, max1+1, i):
            eratosthenes[j] = False

div_a = [x for x in primes if a%x==0]
div_b = [x for x in primes if b%x==0]

common = [x for x in div_a if x in div_b]

ans1 = 1
for c in common:
    ans1 = ans1*c
    
ans2 = ans1 * a//ans1 * b//ans1

print(ans1)
print(ans2)

처음에는 두 수를 소수를 이용해 소인수분해하고 공통의 소인수의 곱이 최대공약수, 그리고 최대공약수*(a에서 최대공약수를 나눈 몫)*(b에서 최대공약수를 나눈 몫) = 최소공배수라는 아이디어로 풀었다. 하지만 위의 코드는 두 수의 최대공약수가 소수의 지수승인 경우를 고려하지 못한다. 예를 들어 a = 8, b = 12일 때, 두 수의 최대공약수는 4이지만 위의 코드는 두 수의 최소공약수를 2로 계산하는 맹점이 있다. 게다가 코드가 길고 복잡해져서, 정답을 참고해 문제를 다시 풀게 되었다.

a, b = map(int, input().split())

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

ans1 = gcd(a, b)

print(ans1)
print(ans1*(a//ans1)*(b//ans1))

코멘트

이 문제는 유클리드 호제법이라고 하는 알고리즘을 사용하는 문제이다. (원리는 영상을 참고하도록 하자) 유클리드 호제법은 다음과 같은 과정을 거쳐서 두 수의 최대공약수를 구하는 알고리즘이다.
Step 1. 두 수 중 큰 수를 작은 수로 나눈다.
Step 2. 나머지가 0이면 작은 수가 최대 공약수이다.
Step 3. 나머지가 0이 아니면 작은 수가 큰 수가 되고, 나머지를 작은 수로 대체하고 Step 1으로 돌아가 과정을 반복한다.
이를 코드로 구현한 것이 위의 gcd 함수이다. 유클리드 호제법을 사용하면 위와 같이 간단하게 최대공약수를 구할 수 있고, 최소공배수도 금방 구해서 정답을 받을 수 있다.

추가

아래는 ChatGPT에 의뢰해서 받은 코드. 아래를 이용하면 소수의 지수승까지 정확하게 계산하여 소인수 분해를 해주므로 이를 바탕으로 처음에 작성한 코드를 보완해서 정답을 받을 수 있겠다.

def prime_factorization(n):
    factors = {}
    divisor = 2
    while n > 1:
        while n % divisor == 0:
            if divisor in factors:
                factors[divisor] += 1
            else:
                factors[divisor] = 1
            n //= divisor
        divisor += 1
    return factors