2유클리드 알고리즘

 

프로그램 5-1은 최대공약수의 정의에 충실할 뿐만 아니라 직관적인 최대공약수 알고리즘입니다. 이번에는 유클리드가 발견한 최대공약수의 성질을 이용하는 다른 알고리즘을 살펴보겠습니다.

수학자로 유명한 유클리드(Euclid)는 최대공약수에 다음과 같은 성질이 있다는 것을 발견하였습니다.

 

• a와 b의 최대공약수는 ‘b’와 ‘a를 b로 나눈 나머지’의 최대공약수와 같습니다. 즉, gcd(a, b) = gcd(b, a % b)입니다.

• 어떤 수와 0의 최대공약수는 자기 자신입니다. 즉, gcd(n, 0) = n입니다.