JS 최대 공배수, 최대 공약수 구하기

최대 공약수 (GCD)

최대 공약수는 두 수 또는 그 이상의 정수의 공통된 약수 중 가장 큰 수입니다. 유클리드 알고리즘을 사용하여 구할 수 있습니다.

function gcd(a, b) {
  while (b !== 0) {
    let t = b;
    b = a % b;
    a = t;
  }
  return a;
}

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

 

유클리드 알고리즘은 두 자연수의 최대공약수(Greatest Common Divisor, GCD)를 찾는 알고리즘입니다. 이 알고리즘은 고대 그리스 수학자 유클리드가 제시한 것으로, "원론"이라는 책에서 처음 소개되었습니다. 유클리드 알고리즘은 효율적이며, 두 수의 크기에 상관없이 빠르게 최대공약수를 계산할 수 있습니다.

 

최소 공배수 (LCM)

최소 공배수는 두 수의 공통된 배수 중 가장 작은 수입니다. 두 수의 곱을 그 수들의 최대 공약수로 나누어 구할 수 있습니다.

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

console.log(lcm(48, 18)); // 144

 

gcd 함수를 사용하여 최대 공약수를 구한 후, 이를 이용해 lcm 함수에서 최소 공배수를 계산합니다.

 

여러 수의 최대 공약수와 최소 공배수

여러 수의 최대 공약수와 최소 공배수를 구하려면, 두 수의 최대 공약수(또는 최소 공배수)를 구하는 함수를 반복적으로 사용하여 모든 수에 대해 적용하면 됩니다.

// 여러 수의 최대 공약수
function gcdMultiple(numbers) {
  return numbers.reduce((a, b) => gcd(a, b));
}

// 여러 수의 최소 공배수
function lcmMultiple(numbers) {
  return numbers.reduce((a, b) => lcm(a, b));
}

console.log(gcdMultiple([48, 18, 64])); // 2
console.log(lcmMultiple([48, 18, 64])); // 576

이 방법을 통해 두 수 뿐만 아니라 여러 수의 최대 공약수와 최소 공배수를 구할 수 있습니다.