[백준 2609] 최대공약수와 최소공배수

두 개의 자연수를 입력받고 최대 공약수와 최소 공배수를 출력하는 간단한 문제이다.

 

최대 공약수는 greatest common divisor의 약자를 사용해서 GCD로 줄여 부르며 최소 공배수는 largest common multiple로 LCM으로 줄여 부른다

 

GCD와 LCM을 구하는 방법은 다양하다

GCD를 구하는 직관적인 방법으로 1씩 증가시키며 두 수에 모두 나누어 떨어지는지 확인하여 가장 큰 수를 찾아내는 방법이 있다. 

for i in range(1,min(x,y)+1):
	if x%i==0 and y%i==0:
    	res = i

이 방법은 O(n)의 시간복잡도를 갖는다

 

시간 복잡도 측면에서 효율적인 방법으로는 유클리드 호제법이 있다

 

x,y의 최대 공약수를  구할 때 유클리드 호제법을 사용하면 큰 수를 작은 수로 나누어 떨어질 때까지 반복해주면 된다

즉, x%y가 0이 나올 때 까지 반복해서 변수를 초기화해주며 나눠주면 된다

while x%y!=0:
	tmp = y
	y = x%y
	x = tmp
GCD = y

나누는 과정을 반복하여 구하기에 시간 복잡도는 O(logN)을 갖는다

 

최소 공배수(LCM)는 구하고자 하는 두 수 x,y를 곱한 수를 최대 공약수로 나누면 된다

 

LCM = x * y / GCD(x,y)