최대공약수, 최소공배수 구하기

이번 포스팅은 최대공약수/최소공배수를 Computer를 이용해서 구하는 방법입니다.

 

1. 단순탐색

 

컴퓨터를 사용하지 않을 경우 구했던 방법을 생각해보면

 

1. a와 b가 있다.

2. a = a_1*a_2*a_3...., b = b_1*b_2*b_3....의 형태로 인수분해 한다.

3. 이때 인수분해 된 값들 중 교집합을 찾는다.

 

Prime Number를 구하는 포스팅을 참고하면, N의 숫자가 있을 때

 

N을 인수분해 하기 위해서는 1~1/N까지의 값으로 N을 나눤서 0이되는 값을 찾아야 합니다.

 

하지만 이 방법은 O(N)의 시간복잡도를 갖기 때문에, 숫자가 커질수록 알고리즘의 성능이 떨어집니다.

 

 

 

2. 유클리드 호제법

다른 방법으로는, 두 수의 나눗셈결과를 이용하는 유클리드호제법이 있습니다.

 

ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

알고리즘을 살펴보면

1. a와 b가 있을 때, a를 b로 나눈다.

1_1. 나머지가 0이면 b가 a와 b의 최대공약수가 된다.

2. 나머지가 0이 아니면 a = b, b = (a를b로 나눈 나머지)로 치환한다.

 

유클리드 호제법 식의 전개(d는 최대공약수)

위 수식을 살펴보면, a와 b가 최대공약수를 이용해서 a', b'로 나눠지게 됩니다.

 

이때 2행에서 3행으로 갈 때 remain이 d의 배수라고 가정 후 식을 전개하게 됩니다.

 

문제는 r''가 정수가 되면 최대공약수로 나눈 a'와 b'는 모두 d'의 배수가 되게됩니다.

 

이 경우 d가 최대공약수 이기 때문에 a', b'가 서로소여야 하지만 모순이 발생하게 됩니다.

 

따라서 d'(b'와 r의 최대공약수)가 1이면 식이 성립하는 것을 알 수 있습니다.

 

그럼 이제 r이 a와 b의 최대공약수를 공유한다는것을 알 수 있게 되었습니다. 

 

이를 활용해서 b와 r사이의 최대공약수를 구해주는 재귀적인 방법으로 a와 b의 최대공약수를 구할 수 있습니다.

 

아래는 유클리드 호재법을 활용해서 최대공약수, 최소공배수는 구하는 Python코드입니다 :)

#최대공약수 구하기
def gdc(a,b):    
    while True:
    	#a와 b를 가지고 나눈 몫과 나머지를 저장합니다.
        temp = divmod(a,b)
        #나눈 나머지가 0이면 해당 나눈 값이 최대공약수가 됩니다.
        if temp[1] == 0:
            return b
            break
        #아닌경우 a는 나눈값으로, b는 나머지로 치환 후 알고리즘을 반복합니다.
        else:
            a = b
            b = temp[1]
            
            
#최소공배수 구하기
def lcm(a,b):
	#두 수 a,b의 최대공약수를 구합니다.
    temp_gdc = gdc(a,b)
    #a와b를 곱한 값에서 최대공약수를 나누면 최소공배수가 나옵니다.
    return int(a*b/temp_gdc)