2609번 백준

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

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

// 최대 공
def GCD(a, b):
    r = a % b
    while(r != 0):
        a, b = b, r
        r = a % b
    return b

a, b = map(int, input().split(' '))
g = GCD(a, b)
print(g, a * b // g, sep="\n") # 최대공배수, 최소공배수 순으로 출력

최대공약수(GCD)와 최소공배수(LCM)를 구하는 문제이다. 이 문제에서는 두 수만 비교하는 문제이므로, 이에 맞춰 설명한다.

GCD함수는 최대공약수를 구하는 함수인데, 구하는 원리는 다음과 같다.

1) a를 b로 나눴을 때의 나머지 r을 구한다.

2) r이 0이 아닌 경우, b와 r의 최대공약수를 구하는 과정으로 넘어간다. 이는 유클리드 호제법에서 a % b = b % r 임을 이용한 것이다.

3) 1과 2를 r == 0일 때 까지 계속 반복한다. r이 0이면, b는 최대공약수가 된다.

 

최소공약수는 최대공약수와 깊은 연관이 있다. 각각의 소인수에 겹치치 않는 인수를 곱해주면 된다. 이를 이용하면, a와 b를 곱하면 겹치는 인수는 최대공약수가 된다. 이때 최대공약수로 나누어주면, 그 수는 최소공배수가 된다.