(파이썬) 최대공약수 구하기

프로젝트 오일러 문제를 풀다보면 두 자연수의 최대공약수를 구해야 하는 경우가 빈번히 발생한다. 이때 유클리드 알고리즘(유클리드 호제법)을 이용하여 쉽게 최대공약수를 구하는 함수를 소개하고자 한다. 

def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while b != 0:
		(a, b) = (b, a % b)
	return a

먼저 \(a\) 쪽이 항상 크도록 해주고, \(a\)와 \(b\) 의 최대공약수는 \(b\)와 \(a\) 를 \(b\)로 나눈 나머지와의 최대공약수와 같기 때문에, 나머지가 \(0\) 이 될때까지 이 작업을 반복해 준다. \(b\) (=나머지)가 \(0\) 일 때의 \(a\) 값이 \(a, \;b\) 의 최대공약수가 된다.