최대 공약수

최대 공약수란 주어진 두 정수의 약수 중에서 가장 큰 공통이 되는 약수를 말합니다.

예를들어 100과 30의 최대 공약수를 구해 봅시다.

100 약수 : 1,2,4,5,10,20,25,50,100
30 약수 : 1,2,3,5,6,10,15,30

이중 공통이 되는 약수는 1,2,5,10 이고 가장큰 최대 공약수는 10입니다.

보통 소인수 분해를 통해 구하게 되는데

2	100	30
5	50	15
	10	3

아래 표와 같이 2와 5로 나눈후 더 이상 떨어지는수가 없어 2 * 5 = 10을
최대공약수로 구합니다.

유클리드 알고리즘

위의 30과 100은 10이라는 최대 공약수를 가집니다. 이 최대 공약수를 G(Greatest Common Divisor) 라고 가정합시다.
A = aG (30 = 3 * 10)
B = bG (100 = 10 * 10)

여기서 a와 b는 G(최대 공약수)를 제외한 값들을 곱한 값을 의미 합니다. 그리고 a와 b는 서로소(공통되는 약수가 1밖에 없는 경우)입니다. 예를들어 3의 경우 약수는 1,3이고 10은 1,2,5,10 입니다. 따라서 공약수는 1입니다.

a-b와 b는 서로소이기 때문에 A-B와 B의 최대 공약수 역시 G입니다. 공식은 아래와 같습니다.

A-B = a * G - b * G = (a-b) *G

함수의 이름은 Greatest Common Divisor의 약자로 GCD로 정하겠습니다.

def GDG(a,b):
    if a < b :
        t = a
        a = b
        b = t
    a = a - b
    print (a, b)
    if (a == 0) :
        print(b)
        return b
    GDG(a,b)

if __name__ == '__main__':
    GDG(30, 100)

스크린샷 2018-05-01 오후 11.27.19.png

유클리드 알고리즘 개선

a와 b값이 차이가 크게 되면 실행시간이 오래 걸립니다. 위의 예제의 경우 6번 실행하면 결과가 나옵니다. 하지만 1과 2000의 최대 공약수를 구할경우 2000번 실행해야 합니다. 따라서 이 문제를 해결해야 합니다.

30과 100의 공약수를 구하는 과정을 보면 (10,30)이 구간 입니다. 이 값을 보면 10은 100/30의 나머지와 동일 합니다.

100 - (30*3) = 10

따라서 %연산을 이용하여 나머지를 구하고 시작한다면 실행횟수를 줄일 수 있습니다.

개선한 코드는 아래와 같습니다.

def GDG(a,b):
    t = a % b
    a = b
    b = t
    print (a, b)
    if (b == 0) :
        print(a)
        return a
    GDG(a,b)

if __name__ == '__main__':
    GDG(30, 100)