최대 공약수 알고리즘

최대공약수(GCD) 구하기 : 유클리드 알고리즘

a, b (a>b) 가 있다고 칠 때
a를 b로 나눈 나머지를 r이라 하자
즉 r은 a%b를 말한다.

• r 이 0이라면 b가 최대공약수이다.
• r 이 0이 아니라면, a=b, b=r로 두고 a를 b로 나눈 나머지 r을 새로 구한다. r이 0이 나올 때, b가 최대 공약수인 것이다.

---

a가 20, b가 15라고 가정 했을 때 이와 같다.

r이 0이 아니므로 a=b, b=r을 수행하고 새로운 r을 얻어낸다.

이제 r이 0일 때, b가 최대 공약수이다. 즉, 최대 공약수는 5 이다.

---

알고리즘 구현 (Python)

while문으로 구현

def gcd(a, b):
    if a < b: # a>b 이도록 스왑한다.
        temp = a
        a = b
        b = temp
    while r>0:
        r = a%b
        a = b
        b = r
    return b

---

재귀함수로 구현
재귀 함수로 구현 시 a=b, b=r의 과정을 좀 더 간결하게 만들 수 있다.

def gcd(a, b):
    if b==0:
        return a
    else:
        return gcd(b, a%b)