수학에 나오는 유클리드 호제법을 사용하여  최대공약수를 구하는 방법을 알아봅니다.

유클리드 호제법은 두 개의 정수 중 큰 수를 작은 수에 나눕니다. 이때 나머지를 가지고 다시 나웠던 수(작은 수)에 다시 나눕니다. 그러면 나머지가 나오는데 이 나머지가 0이 나올때 까지 계속해서 이전의 나머지에 나누게됩니다. 0이 나오게 되는 몫이 바로 두 수의 최대공약수가 됩니다. 이를 순서대로 나타내면 다음과 같습니다.




# 유클리스 호제법을 사용한 최대공약수 구하기
만약 두 수가 54, 76이라면 아래의 절차에 따릅니다.

  • a, b 두 수 중에서 큰 수인 76을 54로 나누기
  • 이때 나머지 22로 54를 나누기
  • 나머지 11로 22를 나누기
  • 계산하면 몫이 2 나머지는 0이므로 최대 공약수는 2임

그럼 위 방법이 맞는지 확인해보겠습니다.

54의 약수 - 1 2 3 6 9 18 27 54
76의 약수 - 1 2 4 19 38 76

같은 약수는 2뿐이므로 유클리드 호제법에 의한 방법과 정확히 일치합니다.



# 유클리드 호제법을 구하는 알고리즘
자바스크립트를 사용하여 구현해보도록 하겠습니다. 먼저 소스코드입니다.
<script>
function getGCD(a, b) {
  if (a < b) {
    c = a; a = b; b = c;
  }
  var restVal = getRest(a, b);
  if (restVal === 0) {
    alert(b);
  }
  else {
    getGCD(b, restVal);
  }
  function getRest(a, b) {
    return a % b;
  }
}
</script>

위  코드를 잠시 설명하면 나머지가 0이되면 값을 return하고 그렇지 않은 경우 재귀함수를 계속해서 실행합니다. 그리고 a<b인 경우 ... 즉 b가 더 큰 경우에는 값의 위치를 바꾸는 코드가 맨 위의 if에 존재합니다.


아래는 실제 위 코드를 적용하여 만들어본 코드입니다. 아래 예제는 a, b 직접 입력해 테스트하는 것이 가능합니다. 직접 눌러보세요!