1. Problem 📃

📚 출처 - 1052-물병

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

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

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

입출력 예

	예제 입력	예제 출력
1	24 18	6 72

2. Logic 👨‍🏫

최대공약수는 유클리드 호제법 알고리즘을 이용해 해결했고, 최소공배수는 앞서 구한 최대공약수를 이용해 해결했다.

최대공약수 (유클리드 호제법)
1. 임의의 두 자연수 a, b가 주어졌을때, 둘 중에 큰 값을 a라고 가정하고 시작합니다.
2. a를 b로 나눈 나머지를 n이라고 한다면, n이 0일때 b가 최대공약수 입니다.
3. 만약 n이 0이 아니라면, a에 b값을 넣고, n을 b에 넣어 다시 2번의 과정을 반복해줍니다.

최소공배수
예를 들어, 12와 8의 최대공약수와 최소공배수를 구해본다면 4와 24가 나옵니다. 12는 2 * 2 * 3, 8은 2 * 2 * 2로 나누어 볼 수 있고, 최소공배수인 24는 2 * 2 * 2 * 3입니다. 앞서 각각 12와 8에는 2 * 2가 공통적으로 존재하는데 이 값은 최대공약수인 4와 값이 같습니다. 나머지 남게 되는 12는 3, 8은 2가 남게 됩니다. 이 값은 각 수를 최대공약수로 나누게 되면 나오는 숫자입니다.
즉, 정리해보자면 다음과 같습니다.
gcd(12, 8) * (12 / gcd(12,8)) * (8 / gcd(12, 8))

3. Code 💻

1. 내가 푼 코드😁

def gcd(a, b): # 최대공약수
    if a < b:
        a, b = b, a
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b): # 최소공배수
    return int(gcd(a, b) * (a / gcd(a, b) * (b / gcd(a, b))))

A, B = map(int, input().split())

print(gcd(A, B))
print(lcm(A, B))