[알고리즘] 최대공약수, 최소공배수, 유클리드 호제법

✅ 최대공약수

1. 완전 탐색(Brute Force)

두 자연수 a, b (a <= b)의 최대공약수를 구할 때 a부터 1까지의 모든 자연수로 두 수를 나누면서 두 수가 나누어 떨어지는 가장 큰 수를 찾는 방법.

 

const gcd = (num1, num2) => {
  const min = num1 < num2 ? num1 : num2;
  for (let i = min; i > 0; i--) {
    if (num1 % i === 0 && num2 % i === 0) {
      return i;
    }
  }
}

 

2. 유클리드 호제법

유클리드 호제법을 이용해 재귀적으로 최대공약수를 구하는 방법.

 

const gcd = (num1, num2) => {
  if (num2 === 0) return num1;
  return gcd(num2, num1 % num2);
}

 

✅ 최소공배수

두 자연수 a, b의 최대공배수는 a * b / (a, b의 최대공약수)라는 공식으로 쉽게 구할 수 있다.

 

const lcm = (num1, num2) => {
  return num1 * num2 / gcd(num1, num2);
}

 

 

✏️ 관련 문제

https://school.programmers.co.kr/learn/courses/30/lessons/120808