1. 문제

출처: 백준 2609번 최대공약수와 최소공배수

2. 풀이

먼저, 각 숫자의 약수들을 구하는 것에서부터 시작한다.

약수들을 오름차순으로 정렬했을 때 양 끝의 약수들끼리 곱하면 원래의 숫자가 나온다.
약수들의 모음이 $[a_1, a_2, a_3, ..., a_n]$라고 할 때, $a_1 \times a_n$, $a_2 \times a_{n-1}...$들은 원래 숫자가 나온다.

따라서, 숫자를 하나씩 올려가면서 약수를 구하려는 숫자를 나눠보고, 나머지가 0이라면 나눈 숫자와 몫을 약수 모음에 넣어주면 된다.

이때 나누는 숫자가 몫보다 커지면, 뒤에 나올 약수들은 반복될 것이므로 멈추면 된다.

모든 약수를 구하고 나면, set을 활용하여 공약수를 구하고 max를 활용하여 최대공약수를 구한다.

그리고, 최소 공배수는 두 수를 곱하고 최대공약수로 나눠주면 쉽게 구할 수 있다.

3. 소스코드

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

num_a = [1,a]
for i in range(2,a//2):
	if i > a//i:
        break
    if a%i==0:
        num_a.append(i)
        num_a.append(a//i)

num_b = [1,b]
for j in range(2,b//2):
	if j > b//j:
        break
    if b%j==0:
        num_b.append(j)
        num_b.append(b//j)

num_a = set(num_a)
num_b = set(num_b)
num_ab = num_a&num_b

GCD = max(num_ab)
LCM = int(a*b/GCD)
print(GCD)
print(LCM)

4. 그 외