[Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

수학자 유클리드(Euclid, BC 4세기~3세기)

 유클리드 호제법을 이용하면 두 수의 최대공약수를 구할 수 있습니다. 최대공약수는 두 수의 공통인 최대 약수를 말합니다.

 

[ Contents ]

 

 

1. 유클리드 호제법 (Euclidean Algorithm)

두 자연수 X, Y가 있을 때 (단, X > Y)
1) X와 Y의 최대공약수는 'X를 Y로 나눈 나머지'와 'Y'의 최대공약수와 같다.
 - 큰 수를 작은 수로 나눈 나머지가 0이 될 때까지 반복

2) X와 Y의 최대공약수는 'X를 Y로 뺀 값'과 'Y'의 최대공약수와 같다.
 - X와 Y가 같아질 때까지 큰 수를 작은 수로 빼며 반복

 

 두 수의 최대공약수는 작은 수로 빼거나, 나눈 나머지로 구한 최대공약수와 같습니다. 

 유클리드 호제법을 이용하면, 1부터 Y까지 공약수 유무를 판별하지 않고도 최대공약수를 구할 수 있습니다. 주로 빼는 방법보다는 '나머지'를 이용해서 적은 연산횟수로 빠르게 구합니다. 

 

 

2. 유클리드 호제법 예시

X: 350, Y: 100 일 때의 최대공약수는?

1번 방법)
 350 % 100 = 50
 100 % 50 = 0
 ∴ GCD(350, 100) = 50

2번 방법)
 350 - 100 = 250
 250 - 100 = 150
 150 - 100 = 50
 100 - 50 = 50
 ∴ GCD(350, 100) = 50

 

 

3. 코드

#1번 방법
def gcd(x, y):
    if x < y:
        x, y = y, x
    while y != 0:
        x %= y
        x, y = y, x
    return x

 

#2번 방법
def gcd(x, y):
    while x != y:
        if x > y:
            x -= y
        else:
            y -= x
    return x