최대 공약수(GCD, Greatest Common Divisor)

A와 B의 공통된 약수 중에 가장 큰 정수를 최대 공약수라고 한다.

// O(N)
const getGCD = (A, B) => {
  let gcd = 1;
  for(let i = 2; i <= Math.min(A, B); i++) {
    if(A % i === 0 && B % i === 0) {
      gcd = i;
    }
  }
  return gcd;
}

유클리드 호제법을 이용한 구현

2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

유클리드 호제법의 기본 원리는 A를 B로 나눈 나머지를 R라고 했을 때, GCD(A, B) = GCD(B, R)과 같다는 것이다.
R이 0이라면, 그 때의 B가 최대 공약수이다.

A = 24, B = 16 이라고 가정해보자.
GCD(24, 16) = GCD(16, 8) = GCD(8, 0)
GCD = 8

const getGCD = (A, B) => B ? getGCD(B,  A % B) : A;
// 여기서 A < B의 경우에는 값이 자동으로 스왑된다.

재귀로 접근하지 않는다면 아래와 같이 구현한다.
시간복잡도 : O(logN)

const getGCD = (a, b) => {
  while(b !== 0) {
    let r = a % b;
    a = b;
    b = r;
  }
  return a;
}

최소 공배수(LCM, Least Common Multiple)

두 수 또는 그 이상의 여러 수의 공통인 배수 중 가장 작은 수.

• 최소공배수는 최대 공약수(GCD)를 응용해서 구할 수 있다.
• 두 수 a와 b의 최소 공배수는 a와 b의 곱을 a와 b의 최대 공약수를 나눈 것과 같다.
• lcm = (a*b) / gcd.
• a * b = gcd * lcm 과 같다는 원리를 이용하는 것이다.

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

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

연습문제

boj 2609 최대공약수와 최소공배수

function solution(n, m) {
  //const gcd = (a, b) => {
    //if(b === 0) return a;
    //return gcd(b, a % b);
  //};
  const gcd = (a, b) => b ? gcd(b, a % b) : a;
  const lcm = (a, b) => a * b / gcd(a, b);
  return [gcd(n, m), lcm(n, m)];
}