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

최대공약수(GCD)

• 두 수가 공통으로 가지고 있는 약수 중 가장 큰 수
• 즉, 두 수를 나눌 수 있는 공통된 수 중 가장 큰 수

최대공약수를 구할 수 있는 가장 쉬운 방법은 1부터 N(a, b 중 작은 수)까지 순회하면서 a와 b를 각각 나누었을 때 그 나머지가 둘 다 0이되는 수, 즉 나누어 떨어지는 수를 찾는 것이다.

이를 바탕으로 자바스크립트로 구현하면 다음과 같이 구현할 수 있다.

function solution(n, m) {
  let gcd = 0; // 최대공약수

  // 최대공약수 구하기
  for (let i = 1; i <= Math.max(n, m); i++) {
    if (n % i === 0 && m % i === 0) {
      gcd = i;
    }
  }

다른 방법으로 유클리드 호제법을 사용하는 방법이 있다.

유클리드 호제법이란?

유클리드에 의해 발견된 가장 오래된 알고리즘으로, 두 수의 최대공약수를 구하는 방법이다.

유클리드 호제법의 원리는 두 수를 나눈 나머지를 r이라고 할 때, 두 수 중 작은 수와 r의 최대공약수가 두 수의 최대공약수와 같다는 것이다. 이러한 과정을 반복하다가 나머지가 0이 될 때 나누는 수가 두 수의 최대공약수인 것이다.

1. 두 수, a와 b를 a % b 로 나눠 나머지 r1이 생기면,
2. 다시 b와 r1을 가지고 b % r1 로 나눠 나머지 r2가 생기면,
3. 또다시 r1과 r2를 가지고 r1 % r2로 나눠 나머지가 0이 된다.

그렇다면 a와 b의 최대공약수는 나머지가 0이 될 대 나누는 수인 r2가 되는 것이다.

예를 들어, 두 수가 58과 30일 때, 58 % 30의 나머지는 28이고, 30 % 28의 나머지는 2이고, 28 % 2의 나머지는 0이므로 58과 30의 최대공약수는 2가 된다.

이를 바탕으로 자바스크립트로 구현하면 다음과 같이 구현할 수 있다.

// 최대공약수 구하기
const gcd = (a, b) => {
  while (b > 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
};

재귀 함수를 활용하면 더 간단하게 구현할 수 있다.

// 최대공약수 구하기
let gcd = (a, b) => (a % b ? gcd(b, a % b) : b);

최소공배수(LCM)

• 두 수가 공통으로 가지고 있는 배수 중 가장 작은 수

즉, 최소공배수는 두 수를 곱한 값을 최대공약수로 나눈 수이므로, 최대공약수를 구할 수 있다면, 최소공배수는 쉽게 구할 수 있다.

function solution(n, m) {
  let gcd = 0; // 최대공약수
  let lcm = 0; // 최소공배수

  // 최대공약수 구하기
  for (let i = 1; i <= Math.max(n, m); i++) {
    if (n % i === 0 && m % i === 0) {
      gcd = i;
    }
  }

  // 최소공배수 구하기
  lcm = (n * m) / gcd;

  return gcd, lcm;
}

// 최대공약수 구하기
const gcd = (a, b) => {
  while (b > 0) {
    let temp = b;
    b = a % b;
    a = temp;
  }
  return a;
};

// 최소공배수 구하기
const lcm = (a, b) => {
  return (a * b) / gcd(a, b);
};