[구현/수학] 백준 13241 최소공배수

[ Contents ]

1. 문제 (링크 참조)

13241번: 최소공배수

정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다

www.acmicpc.net

최소 공배수를 구하는 문제입니다. 최소공배수는 '두 수의 곱 / 최대공약수' 입니다.

[Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

유클리드 호제법을 이용하면 두 수의 최대공약수를 구할 수 있습니다. 최대공약수는 두 수의 공통인 최대 약수를 말합니다. [ Contents ] 1. 유클리드 호제법 (Euclidean Algorithm) 두 자연수 X, Y가 있을

star7sss.tistory.com

최대공약수는 유클리드 호제법을 이용해서 빠르고 쉽게 구할 수 있습니다. 방법론과 코드는 위 링크에 설명되어 있습니다.

# 입력
A, B = map(int, input().split())
res = A*B

# 최대공약수 (유클리드 호제법)
while B:
    if A > B:
        A, B = B, A
    B %= A

# 최소공배수
print(res//A)

유클리드 호제법을 이용해서 최대공약수를 구하고, 구한 최대공약수를 이용해서 최소공배수를 구합니다.