유클리드 호제법

위키백과에 따르면, 유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나입니다.
호제법이라는 말은 서로(호) 상대방의 수를 나누어(제)서 결국 원하는 수를 얻는 알고리즘을 말합니다.
두 개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 한다면, a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. (a > b)

위키백과에 좋은 예가 있습니다.

1071과 1029의 최대공약수를 구하는 과정입니다.
1. 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구합니다. >> 42
2. 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구합니다. >> 21
3. 42는 21로 나누어 떨어집니다.

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

즉, a를 b가 나누어 떨어지지 않는다면, 그 나머지 r을 구하고, b를 r로 나눕니다.
나누어 떨어지지 않는다면, 그것의 나머지를 구하고 r을 그 나머지로 나눕니다.
나누어 떨어질 때까지 반복을 해서 나온 값이 a와 b의 최대공약수인 것입니다.

아래의 코드는 유클리드 호제법을 이용해서 최대 공약수를 구하는 함수입니다.

function gcd(a, b) {
  return (a % b) === 0 ? b : gcd(b, a % b);
}

a를 b로 나누었을 때 나머지(r)가 0이라면 b를 취하고, 그렇지 않다면 b를 r로 나누어 자기 자신을 다시 호출합니다. 나누어 떨어질 때야 비로소 함수가 동작을 멈추고 최대공약수를 리턴합니다.