백준 boj 2609 - 최대공약수와 최소공배수 (파이썬, python)

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

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

역시 이 문제 또한 일반 반복문을 통하여 해결하였을 때에는 시간초과로 틀리게 된다...

유클리드 호제법이란 것을 활용해야 하는데,

 

유클리트 호제법이란 x, y의 최대공약수는 y, x % y 의 최대공약수와 같다는 원리를 이용한다.

x % y 의 값이 0이 됐을 때의 y 값이 결국 최대 공약수가 된다.

 

이게 뭔소리냐면...

10 과 6 을 예시로 든다면,

 

x	y	x%y
10	6	4
6	4	2
4	2	0

 

결국, 최대 공약수는 2 이다.

 

증명은 나무위키에 잘 나와 있다.

https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95

 

최소 공배수는 주어진 값들의 곱을 최대 공약수로 나눠주면 된다.

 

code

n, m = map(int, input().split())

def gcd(x, y):
    while(y):
        x, y = y, x % y
    return x
print(gcd(n,m))

def lcm(x, y):
    result = (x * y) // gcd(x, y)
    return result
print(lcm(n, m))