[🥈5 / 백준 2609 / 파이썬] 최대공약수와 최소공배수

 

2609번: 최대공약수와 최소공배수

 

문제

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

입력

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

출력

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

 

예제 입력 24 18

예제 출력 6 72

 

풀이

 

주어진 수의 최소공배수와 최대공약수를 구하는 문제이다.

 

입력의 범위가 최대 10000으로 그렇게 크지 않기 때문에

 

최대공약수는 사실 아무렇게나 구해도 상관없다.

 

하지만 최소공배수를 구함에 있어서 그냥 1씩 더해가며 나눠서 비교한다면 TLE 를 피할 수 없을 것이다.

 

 

최소공배수를 구하는 방법을 먼저 알아보자.

 

24 = 2³ * 3

18 = 2 * 3²

 

위같이 수를 소인수 분해해서 나타낼 수 있다.

 

그리고 각 소인수 중에서 지수가 가장 큰 것들과 나머지를 곱하면 최소공배수를 구할 수 있다.

 

2³ * 3² = 72

 

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

# 최대공약수
for i in range(min(a,b),-1,-1):
    if a%i == 0 and b%i == 0:
        print(i)
        break

# 최소공배수
p,q = [],[]

# a 소인수분해
while(True):
    for i in range(2,a):
        if a%i == 0:
            p.append(i)
            a //= i
            break
    else:
        p.append(a)
        break

# b 소인수분해
while(True):
    for i in range(2,b):
        if b%i == 0:
            q.append(i)
            b //= i
            break
    else:
        q.append(b)
        break
        
r = [0] * (max(max(p),max(q))+1)
s = list(r)
# a와 b의 소인수들의 지수를 담을 배열

result = 1
for i in p:
    r[i] += 1
for i in q:
    s[i] += 1
for i in range(len(r)):
    result *= i**max(r[i],s[i])
    # 두 수의 소인수의 지수 자리를 비교하며
    # 지수가 더 큰 것들만 곱해준다.
print(result)

 

위처럼 직접 최소공배수를 구하는 법 말고 훨씬 간단한 방법이 있는데,

 

a와 b 의 최대공약수를 c라고 하자.

 

a*b / c를 하면 최소공배수가 나온다.

 

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

for i in range(min(a,b),-1,-1):
    if a%i == 0 and b%i == 0:
        print(i,a*b//i,sep = "\n")
        break