최대공약수 & 최소공배수 (feat. 유클리드 호제법)

📌 최대공약수 (GCD)

두 수(num1, num2)의 약수 중 공통의 가장 큰 정수 ex) ( 3, 12 ) = 3

JS로 최대공약수를 가장 쉽게 구하는 법은 2부터 증가하면서 두 수 중 가장 작은 수 까지 반복하는 것이다. 

 

function getGcd(num1, num2) {
  let gcd = 1;
  for (let i = 2; i <= Math.min(num1, num2); i++) {
    if (num1 % i === 0 && num2 % i === 0) {
      gcd = i;
    }
  }
  return gcd;
}

 

---

📌 최소공배수 (LCM)

두 수(num1, num2)의 공통 배수 중 가장 작은 정수 ex) ( 3, 12 ) = 12

하나의 변수를 1부터 점차 증가하면서 변수에 두 수를 나누었을 때 나머지가 0이 되는 수를 찾으면 된다  

 

function getLcm(num1, num2) {
  let lcm = 1;

  while (true) {
    if (lcm % num1 === 0 && lcm % num2 === 0) {
      break;
    }
    lcm++;
  }

  return lcm;
}

---

📌 유클리드 호제법

num1를 num2로 나눈 나머지를 r이라고 했을 때, GCD(num1, num2) = GCD(num2, r)과 같다는 것을 기반으로 한다.

 

ex01) num1 = 24, num2 = 16 -> GCD(24, 16) = GCD(16, 8) = GCD(8, 0) = 8

ex02) num1 = 30, num2 = 4 -> GCD(30,4) = GCD(4, 2) = GCD(2, 0) = 2 

ex03) num1 = 54, num2 = 9 -> GCD(54,9) = GCD(9, 0) = 9

 

이때, num2가 0이 될 때까지 반복하다 보면 결국 num1의 값이 두 수의 최대공약수인 것을 알 수 있다. 

이러한 규칙을 이용하여 유클리드 호제법을 이용한 최대공약수 구하는 방법은 아래와 같다. 

 

function getGcd(num1, num2) {
  return num2 > 0 ? getGcd(num2, num1 % num2) : num1;
}

 

그리고, 유클리드 호제법 이론으로 최소 공배수를 구하는 방법은 num1 * num2 = lcm * gcd 공식을 이용하면 된다. 

우리는 lcm 을 구해야 하니 위의 수식을 이용한 결과로는 lcm = (num1 * num2) / gcd 를 구할 수 있다. 

 

그렇기에 총 정리를 해보자면, 아래와 같은 코드가 나온다. 

function getGcdLcm(num1, num2) {
  const getGcd = (a, b) => (b > 0 ? getGcd(b, a % b) : a);
  const getLcm = (a, b) => (a * b) / getGcd(a, b);

  return [getGcd(num1, num2), getLcm(num1, num2)];
}