자바스크립트로 최대공약수 구하는 알고리즘 구현 (greatest common divisor in javascript)

최대공약수(greatest common divisor GCD)

최대공약수의 사전적인 의미는 공약수 중 최댓값을 의미합니다. 두 수의 공약수를 구한 후 그중에서 가장 큰 값을 최대공약수로 구하면 됩니다.

• 약수 ? 어떠한 수나 식을 나머지 없이 나눌 수 있는 수
• 공약수 ? 두 수의 각각의 약수 중 공통된 약수를 의미

우선 약수를 구하는 로직을 작성해보겠습니다.

자바스크립트로 약수 구현 알고리즘

export function getDivisor(value) {
  if (typeof value !== "number") {
    return;
  }
  let result = [];

  for (let i = 1; i <= value; i++) {
    if (value % i === 0) {
      result.push(i);
    }
  }

  return result.toString();
}

console.log(getDivisor(30)); // 1,2,3,5,6,10,15,30
console.log(getDivisor(12)); // 1,2,3,4,6,12

다음으로는 최대공약수를 구하는 로직을 작성해보겠습니다. 약수를 구하는 로직을 조금 수정하면 최대공약수를 구하는 로직을 구현할 수 있습니다.

자바스크립트로 최대공약수 구현 알고리즘

// 최대공약수 구현 함수
export function getGCD(value1, value2) {
  if (typeof value1 !== "number" || typeof value2 !== "number") {
    return;
  }
  // value1과 value2 중 큰 값을 기준으로 값을 선택
  let num = value1 > value2 ? value1 : value2;
  let max;

  for (let i = 1; i <= num; i++) {
    if (value1 % i === 0 && value2 % i === 0) {
      max = i;
    }
  }

  return max;
}
console.log(getGCD(280, 30)); // 10
console.log(getGCD(12, 4)); // 4