백준 2436 공약수

사전 지식

• 최대공약수 구하는 방법
  • x, y의 공약수는 y 와 x%y 의 공약수임.
  • x = y, y = x, r = x%y 를 반복해서 최소의 공약수 찾기.
• 최소공배수 구하는 방법
  • x * y를 최대공약수로 나누기.
• 모든 약수 구하기
  • int( 숫자 ** 0.5 ) 까지 1부터 모든 수로 나눠가며 나머지가 0인 값 찾기.

과정

• 주어진 수 A를 최대공약수로, B를 최소공배수로 갖는 두 자연수 구하기
• 해당하는 수가 많은 경우, A와 B의 합이 가장 작은 경우만 출력

1. x * y = 최소공배수 최대공약수임. 따라서 A B의 모든 약수 쌍을 구함.
2. 모든 약수 쌍에 대해서 최대공약수를 구하고, 이 값이 A인 경우, 조건 만족.

• 조건을 만족하는 값이 여러 개인 경우, 합이 최소인 값을 출력하라 했으니, 리스트 순회 방향 주의

div, comp = map(int, input().split())

div_comp = div * comp

# 최대공약수와 최소공배수의 곱은 x와 y의 곱과 같음
# 최대공약수와 최소공배수 곱의 약수 쌍 찾기

div_lst = []
for i in range(1, int(div_comp ** 0.5) + 1):
    if div_comp % i == 0:
        div_lst.append([i, div_comp // i])


def com_div(x, y):
    r = x % y
    while r != 0:
        x = y
        y = r
        r = x % y
    return y

for i in div_lst[::-1]:
    if com_div(i[0], i[1]) == div:
        print(i[0], i[1])
        break