(정수론/파이썬) 최대공약수 구하는 gcd 함수 구현

파이썬에 보면, numpy 에 최대공약수 구하는 gcd() 함수가 있다.

import numpy as np

print(np.gcd(18, 15))

 

결과: 3

 

이상준 교수님의 다음 강좌를 보다가 gcd 계산법을 알려주시길래 파이썬 코드로 간단하게 짜보았다.

 

https://youtu.be/eI9-fYz4_w4?t=1671

 

이 부분을 코딩하자면, 언뜻 보면 i-1, i+1, i, i+1 등의 인덱스 때문에 넘파이 배열을 만들어 (배열 크기는 a, b 중 작은 수 기준으로) 처리하면 될 듯하지만, 제법 번거롭다. gcd 값만 구하면 되기 때문에 변수를 몇 개만 만들어 사용해도 된다.

 

최초의 r0 = a, r1 = b 라고 하고, r0(처음엔 a값임)을 r1(처음엔 b값임)으로 나눈 나머지를 r2라고 한다. 몫은 필요 없으므로 버린다. 나머지, 즉 r2가 0면 앞의 나머지, 즉 r1이 최대공약수가 된다. 처음 한번 나누어 나머지가 0이 아니라면, 이제 r1값을 r0에 넣고, r2값을 r1에 넣어 반복 루프를 돌린다.  반복 횟수는 a, b 중 작은 값을 기준으로 했고, 결국 나머지가 0이 된다면, 직전의 나머지가 최대공약수 gcd가 되므로 그값을 반환한다.

 

이런 shift 방식 변수 관리 방법은 변수 갯수를 적게 하고 효율적으로 작업할 수 있다는 장점이 있지만, 변수값을 덮어쓰게 되므로 그 shift하는 순서를 조심해야 한다. 

# 유클리드 호제법
# 두 수 a와 b (단 a > b) 의 최대공약수 구하기

def my_gcd(a, b):

    if a == b:
        return a
    if a < b:  # a > b 조건을 맞추기 위해 두 값을 맞바꾸기
        tmp = a
        a = b
        b = tmp
    
    r0 = a
    r1 = b
    for i in range(b): # 두 수 증 작은 수만큼 최대 반복
        r2 = r0 % r1 # 몫은 필요 없으므로 나머지만 구함
        
        if r2 == 0: # 나머지가 0이라면
            return r1 # 직전의 나머지가 최대공약수임
        # 값들을 한칸씩 shift 시켜서 다시 반복
        r0 = r1
        r1 = r2


print(my_gcd(81, 9)) # 9
print(my_gcd(1160718174, 316258250)) # 1078
print(my_gcd(143, 227))   # 1
print(my_gcd(16, 20)) # 4
print(my_gcd(12378, 3054))  # 6