[Javascript] 유클리드 호제법을 활용한 최대공약수(GCD), 최소공배수(LCM) 구하기

function getGCD(input) {
  if (input[0] < input[1]) {
    let temp = input[0];
    input[0] = input[1];
    input[1] = temp;
  }

  let r = input[0] % input[1];
  input[0] = input[1];
  input[1] = r;

  if (input[1] === 0) {
  } else {
    getGCD(input);
  }
  return input[0];
}

function getLCM(nums, gcd) {
  let lcm = (nums[0] * nums[1]) / gcd;
  return lcm;
}

let nums = [500, 100];
let inputNums = [...nums];
let gcd = getGCD(inputNums);
console.log(`======> 최대공약수(GCD) : ${gcd}`);

let lcm = getLCM(nums, gcd);
console.log(`======> 최소공배수(LCM) : ${lcm}`);

 

유클리드 호제법

 

1. 최대공약수 구하기

 

주어진 두 수 a, b(a>b)이고, 몫은 G, 나머지는 r이라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같다는 원리를 이용해 재귀로 풀이하였다.

 

2. 최소공배수 구하기

 

처음 주어진 두 수 a, b를 곱하고 최대공약수로 나누어주면 된다. 최대공약수를 구하면 매우 간단하지만 함수로 묶어줬다.

 

 

---

최소공배수 재귀 없이 풀기

function getLCM(inputNums) {
  let result = 1;
  if (inputNums[0] > inputNums[1]) {
    let temp = inputNums[0];
    inputNums[0] = inputNums[1];
    inputNums[1] = temp;
  }

  for (let i = 2; i <= inputNums[0]; i++) {
    while (inputNums[0] % i == 0 && inputNums[1] % i == 0) {
      inputNums[0] /= i;
      inputNums[1] /= i;

      result *= i;
    }
  }
  result *= inputNums[0] * inputNums[1];
  return result;
}

// let nums = [30, 80];
// let inputNums = [...nums];
// let lcm = getLCM(inputNums);
// console.log(`lcm : ${lcm}`);

 

함수에 인자로 들어온 배열을 [0]번째로 작은 수를 보내주었고, [0]번째 수를 기준으로 루프를 돌려주었다.

왜냐하면 어차피 나눠지는 수는 작은 수를 기준으로 나눠지기 때문이다.

그리고, 나눠지는 i값들을 누적곱을 해준 후 마지막에 남은 배열 내 수들까지 곱해주었다.

 

실제로 우리가 가장 흔하게 계산하는 ㄴ자로 나오는 수를 모두 곱해주는 방식을 코드에 적용해보았다.