유클리드 호제법이란?

유클리드 호제법(Euclidean algorithm)이란 두 개의 정수의 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘이다.

유클리드 호제법은 다음과 같이 작동한다

1. 두 개의 입력 정수를 A와 B라고 가정한다.

2. A를 B로 나눈 나머지를 구한다.

3. 만약 나머지가 0이라면, B가 최대공약수이다.

4. 만약 나머지가 0이 아니라면, A에는 이전 단계에서의 B 값을 대입하고, B에는 이전 단계에서의 나머지 값을 대입한 후 2번으로 돌아간다.

5. 이 과정을 반복하면서 나머지가 0이 될 때까지 계속해서 실행한다. 마지막으로 남은 값인 B가 최대공약수(GCD)가 된다.

예를 들어, A = 48, B = 18인 경우 유클리드 호제법을 적용해보자.

1단계: A = 48, B = 18

2단계: A를 B로 나눈 나머지는 12 (48 % 18)

3단계: A = 18, B = 12

4단계: A를 B로 나눈 나머지는 6 (18 % 12)

5단계: A = 12, B =6

6단계: A를 B로 나눈 나머지는 0 (12 %6)

결론 GCD(48 ,18)은 최대공약수인 "6" 이다.

이를 자바스크립트로 표현하면 아래와 같다.

function euclideanAlgorithm(a, b) {
  // 만약 b가 0이라면, a가 최대공약수이므로 a를 반환합니다.
  if (b === 0) {
    return a;
  }

  // 나머지를 계산하여 변수 temp에 저장합니다.
  const temp = a % b;

  // 재귀적으로 euclideanAlgorithm 함수를 호출하여 값을 계속 업데이트합니다.
  return euclideanAlgorithm(b, temp);
}

// 예시로 GCD(48,18)을 계산해보겠습니다.
const result = euclideanAlgorithm(48, 18);
console.log(result); 
// 출력: 6