[백준 13241번] 최소공배수 python

두 자연수의 최대 공약수를 효율적으로 찾는 알고리즘으로

유클리드 호제법이 있다.

 

1. 나머지 연산을 사용한 반복 

두 수 a, b (a > b)에 대해서, a를 b로 나누어 나머지를 구한다.

나머지를 r이라 할 때,

a와 b의 최대공약수는 b와 r의 최대 공약수와 같다.

 

2. 반복 과정 

b와 r에 대해 같은 과정을 반복한다. b를 r로 나눈 나머지를 구하고,

이를 새로운 r로 사용한다. 나머지가 0이 될 때까지 반복한다.

 

3. 최대 공약수 결정 

나머지가 0이 되면, 나누는 수가 a와 b의 최대 공약수가 된다.

나머지가 0이 되었다는 것은 바로 전 단계의 나누는 수가 나누어지는 수의 약수라는 것을 

의미하고 이는 두 수의 공통된 약수 중 가장 큰 값이 된다.

 

ex) 48과 20

48 % 20 = 8

r = 8 이라고 하면

20 % 8 = 4

r = 4이라고 하면

8 % 4 = 0

 

따라서 최대 공약수는 4가 됨.

---

최대 공약수 * 최소 공배수 = 두 수의 곱

을 이용해본다.

 

[최종 코드]

def gcd(a, b):

    while b!=0 :

        a, b = b, a % b

    return a

def lcm(a, b):

    print(a * b // gcd(a, b))

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

lcm(A, B)