유클리드 호제법, 최대공약수(GCD) 구하기

유클리드 호제법이란

최대공약수를 구하기 위해서는 유클리드 호제법을 사용하면 된다.

호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다.

 

https://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

 

 

 

먼저 1071을 1029로 나눈다. 42라는 나머지가 나온다.

만약 1029가 42로 나누어진다면 1071 = 42 * n이 될텐데 42로 안나눠지니까 42는 최대공약수가 될 수 없다.

 

그 후 1029을 42로 나눠서 21을 얻는다.

이때 42는 21로 나누어지기 때문에 21을 약수로 가진다.

따라서 최대공약수는 21이다.

 

글로 읽으면 복잡한데 결국 1071은

1071 = (1029 * 1) + 42

        = ((42 * k) * 1) + 42

        = (((21*2) *k) *1) + (21*2)

        = 21 * (k+2)

로 쓰일수 있다는걸 생각해보면 이해하는데 도움이 된다.

 

 

 

파이썬 코드

def gcd(a, b):
    while b is not 0:
        mod = a % b
        a = b
        b = mod
        
    return a

 

참고로 파이썬에는 이미 GCD 모듈이 있다.

from math import gcd
result = gcd(a, b)

 

 

여러 수의 최대공약수

세 개 이상의 최대공약수를 구할때는 두개씩 구해주면 된다.

result = gcd(gcd(a, b), c)