유클리드 호제법 - 최대공약수GCD, 최소공배수LCM 구하기

백준 문제를 풀다보면 공약수, 공배수를 활용하는 문제들을 찾아볼 수 있다.
그중 최대 공약수GCD(Greatest Common Divisor), 최소 공배수LCM(Least Common Multiple)를 구하는 문제들이 있는데 
이 경우 유용하게 이용할 수 있는 정의가 있는데 바로 '유클리드 호제법'이다.
유클리드 호제법은 유클리드의 원론에 적혀있는 정의로 한국 수학교육과정에서는 자세하게 다루지 않는 내용이다.

유클리드 호제법을 통해 최대 공약수를 간단하게 구할 수 있다. 

# 최대 공약수 GCD(Greatest Common Divisor)

자연수 a,b가 주어졌을때 
a 를 b로 나눈 나머지가 r인 경우 a,b의 최대 공약수와 b와 r의 최대 공약수가 동일하다

이를 응용하면 

a를 b로 나눈 나머지 r을 구하고
b를 r로 나눈 나머지를 r'구하고 
이를 계속 반복해서 
나머지가 0일 경우 나누는 값은 a,b의  최대 공약수가 된다. 

 

 

코드로 짧게 구현하면 

자연수를 하나씩 접근하여 나눠서 최대공약수를 구하는 알고리즘의 시간복잡도는 O(N)인 반면
유클리드 호제법을 이용하면 O(logN)의 시간복잡도를 가지게 된다. 

# 최소 공배수 LCM(Least Common Multiple)

그렇다면 최소 공배수는 어떻게 구할 수 있을까?
이또한 간단하게 접근할 수 있다. 

두자연수의 곱 = 최소공배수 X 최대공약수 
즉, 최소공배수 = 두자연수의곱 / 최대공약수 

우리는 이미 유클리드 호제법을 이용하여 최대공약수를 구했으므로 
최소공배수는 주어진 정보를 이용하여 쉽게 구할 수 있다.

 

관련문제

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

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