자바스크립트 유클리드 호제법으로 최대공약수, 최소공배수 구하기

유클리드 호제법이란?

유클리드 호제법(Euclidean algorithm)은 두 자연수 또는 정수의 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘입니다. 이 방법은 매우 오래되었으며, 기본적인 원리는 두 수의 차이를 이용해 최대공약수를 찾는 것입니다. 더 현대적인 버전에서는 나눗셈을 사용하여 더 빠르게 최대공약수를 찾습니다. 여기서는 나눗셈을 사용하는 방식으로 설명하겠습니다.

 

 

유클리드 호제법 적용 방법

1. 두 수를 준비합니다. 두 자연수 A와 B를 준비하며, A가 B보다 크거나 같다고 가정합니다. (A ≥ B)
2. 나눗셈을 수행합니다. A를 B로 나눈 나머지를 구합니다. (A % B)
3. 종료 조건을 확인합니다. 나머지가 0이면, B가 최대공약수(GCD)가 됩니다.
4. 숫자를 교체합니다. 나머지가 0이 아니면, A에 B를, B에 나머지를 할당하고 2단계로 돌아갑니다.

이 과정을 나머지가 0이 될 때까지 반복하면, 마지막으로 나누어 떨어진 수(B)가 두 수의 최대공약수가 됩니다.

 

 

유클리드 호제법으로 최대공약수 구하기

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

console.log(gcd(48, 18));

 

이 코드에서 gcd 함수는 두 개의 매개변수 a와 b를 받습니다. 만약 b가 0이면, a가 최대공약수이므로 a를 반환합니다. b가 0이 아니면, 함수는 자기 자신을 b와 a % b(a를 b로 나눈 나머지)를 사용하여 다시 호출합니다. 이 과정은 b가 0이 될 때까지 반복되며, 이때의 a가 두 수의 최대공약수가 됩니다.

유클리드 호제법으로 최소공배수 구하기

최소공배수(Least Common Multiple, LCM)는 두 자연수의 공통되는 배수 중 가장 작은 수를 말합니다. 유클리드 호제법을 활용하여 최대공약수(GCD)를 구한 후, 이를 이용해 최소공배수를 효율적으로 계산할 수 있습니다. 두 수 A와 B의 최소공배수는 A와 B의 곱을 A와 B의 최대공약수로 나눈 값과 같습니다. 이 방법은 두 수의 곱에서 공통된 약수를 제거함으로써 최소공배수를 찾는 원리에 기초합니다.

 

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

function lcm(a, b) {
    return (a * b) / gcd(a, b);
}

console.log(lcm(3, 32));

 

위 코드에서 lcm 함수는 두 매개변수 a와 b를 받아, 두 수의 최소공배수를 계산하여 반환합니다. 예를 들어, lcm(3, 32)의 결과는 3과 32의 최소공배수인 96을 출력합니다. 이 방법을 사용하면 두 자연수의 최소공배수를 간단하고 효율적으로 구할 수 있습니다.