38. 최대공약수, 최소공배수, 그리고 유클리드 호제법 / 파이썬

최대공약수(gcd):

유클리드 호제법이 가장(?) 빠른 계산법으로 알려져 있습니다.

 

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


print(gcd(78696, 19332))

 

최소 공배수(lcm)는 a * b / gcd

def lcm(a, b):
    return (a*b)//gcd(a, b)

 

인류 최초의 알고리듬

 

유클리드(Euclid)는 그리스 수학자 에우클리데스(Ευκλείδης)의 영어식 표현입니다. 

유클리드는 기원전 3세기경 (기하학) 원론 이라는 책을 썼고, 원론 7권 첫 부분에 유클리드 호제법이 실려있습니다. 

 

호제법(互除法)이란

서로(互) 덜어낸(除)다는 뜻입니다. 

덜어낼 때는 나누어서 몫만 남깁니다. 

프로그래밍 언어에서는 보통 mod 라고 표현하죠. 

 

호제법의 예

10과 6의 최대 공약수를 호제법으로 찾는다면.

10을 6으로 나눈 나머지는 4입니다. 

6을 4로 나눈 나머지는 2입니다. 

4를 2로 나눈 나머지는 0입니다. 

그러므로 최대 공약수는 2가 됩니다. 

 

이를 그림으로 나타내면 다음과 같습니다.

아주 직관적입니다. 

증명은 생략하겠습니다. ^^

 

참고

파이썬은 친절합니다. math.gcd가 있습니다.

3.5 이하에선 fractions.gcd 였으나 디프리케이티드 되고, math로 이사 옴...
https://docs.python.org/ko/3/library/math.html#math.gcd

math — Mathematical functions — Python 3.8.5 문서