[Algorithm] 백준 2609번 최대공약수와 최소공배수 (Python)

https://www.acmicpc.net/problem/2609

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

문제

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

입력

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

출력

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

예제 입력 1

24 18

예제 출력 1

6
72

풀이

설명

• 최소공배수(LCM) 계산 전에 먼저 최대공약수(GCD)를 구한다.
• GCD 계산 시 유클리드 호제법(Euclidean algorithm)을 사용한다.
  • a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a, b) = GCD(b, r)
  • r이 0이면 그 때 b가 최대 공약수이다.
  • ex) GCD(24, 16) = GCD(16, 8) = GCD(8, 0) = 8
• LCM = A*B/GCD(A, B)

코드

def GCD(A : int, B : int) :
    if B == 0 :
        return A
    else :
        return GCD(B, A%B)

def LCM(A : int, B : int) :
    return (A*B)//GCD(A, B)

T = list(map(int, input().split(" ")))

print(GCD(T[0], T[1]))
print(LCM(T[0], T[1]))