[백준알고리즘] 2609번: 최대공약수와 최소공배수 -Python

[백준알고리즘] 2609번: 최대공약수와 최소공배수 -Python

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

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

이번 문제는 주어진 두 수에 대한 최대공약수와 최소공배수를 구하는 문제이다. 이전에도 풀었던 문제인데 코드를 비교해보니 거의 같았다. 공식이 있어서 그런 것 같다.

 

최대공약수를 구하는 공식은 유클리드 호제법이다. 유클리도 호제법을 이용하면 다음과 같은 공식이 나오게 된다.

두 수 A와 B가 있을 때, A에 대하여 B를 나눈 몫이 X, 나머지가 R이라 하면, "A = B * X + R"의 식이 나오게 된다. 이때, A와 B의 최대공약수 GCD(A, B)는 다음과 같이 구할 수 있다. (A >= B)

GCD(A, B) = GCD(B, R)

유클리드 호제법 위키

 

즉, A와 B의 최대공약수는 B와 A를 B로 나눈 나머지의 최대공약수와 같다.

 

이 공식을 이용해 최대공약수를 구하고, 최대공약수가 G일 때, A와 B는 각각 a*G, b*G로 표현할 수 있고, 최소공배수는 LCM(A, B) = a*b*G = (A*B)//G 가 된다. 

 

import sys

N, M = map(int, sys.stdin.readline().split())
(X, Y) = (M, N) if M > N else (N, M)

# get GCD
while X % Y:
    X, Y = Y, X%Y

sys.stdout.write(str(Y) + "\n")
sys.stdout.write(str(N*M//Y))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다