유클리드 호제법 은 두개의 자연수의 최대 공약수 를 구하는 알고리즘이다.

• 최대 공약수(GCD: gratest common divisor) 란 두개(혹은 이상) 의 자연수의 공통된 약수 이다.

• 약수(divisor) 란 어떤 자연수를 나누었을 때 나누어 떨어지게 하는 자연수이다.

  • 12의 약수: 1, 2, 3, 4, 6, 12
  • 18의 약수: 1, 2, 3, 6, 9, 18
  • 자연수 12 와 자연수 18의 약수: 1, 2, 3, 6
  • 자연수 12 와 자연수 18의 최대 공약수: 6

원리

• 두개의 자연수(x = 1071, y = 1029) 가 있다.
• 큰 수(y = 1071) 를 작은 수(x = 1071) 로 나눈 나머지를 r 이라고 하자.(y % x = r)
• 작은 수(x = 1071) 는 큰 수(y = x) 로 대입하고, 나머지(r) 는 작은 수로 대입한다.(x = r)
• 나머지가 0 일 될때가지 반복하고 0 될 때의 작은 수(x)의 값이 최대 공약수가 된다.

1071 % 1029 = 42
1029 % 42 = 21
42 % 21 = 0
[최대공약수 = 21]

코드 적용

const euclideanAlgorithm = (x, y) => {
  let temp, r

  // 큰값을 x 에 담는다.
  if (x < y) {
    temp = x
    x = y
    y = temp
  }

  // 나머지가 0 이 되기 전까지 반복문을 실행한다.
  while (y !== 0) {
    r = x % y
    x = y
    y = r
  }

  return x
}

// 재귀적 방법
const recEuclideanAlgorithm = (x, y) => {
  if (y === 0) return x
  else return recEuclideanAlgorithm(y, x % y)
}

const getGratestCommonDivisor = euclideanAlgorithm(1029, 1071)
const getGratestCommonDivisorWithRec = recEuclideanAlgorithm(73870, 10383800)

console.log(getGratestCommonDivisor)
// 21
console.log(getGratestCommonDivisorWithRec)
// 10