최대 공약수와 최소 공배수 구하기

알고리즘 문제를 풀다가 javascript로 최대 공약수와 최소 공배수를 구할 일이 종종 생길 것 같아서 정리할 필요를 느꼈다.

일단 간단하게 설명부터 하고 넘어가겠다.

• 최대 공약수: 두 수 A와 B의 공통된 약수 중에 가장 큰 정수이다.
• 최소 공배수: 두 수, 혹은 그 이상의 여러 수의 공통인 배수 중 가장 작은 수이다.

두 가지 모두 주어진 수에서 1을 증가하거나 감소시켜서 찾을 수 있지만, 알고리즘 문제에서는 해당 접근 방식으로는 시간 복잡도 제한을 해결할 수가 없다.

따라서 유클리드 호제법을 이용한 최대 공약수와 최소 공배수를 구해 볼 것이다.

유클리드 호제법

유클리드 호제법은 두개의 자연수의 최대 공약수를 구하는 알고리즘이다. 정리를 해보면 다음과 같다.
두 수 A, B가 주어질 때, A와 B의 최대 공약수를 gcd(A, B)라고 하면 다음이 성립된다.

gcd(A, B) = gcd(B, r)

이 때, r은 A를 B로 나눈 나머지이다.

최대 공약수 구현

알고리즘 공식을 알았으니, 이제 최대 공약수를 구하는 함수를 만들어 보자.

function gcd(a, b) {
  if (b > 0) {
	return gcd(b, a % b);
  }
  return a;
}

반복문을 통해 구현하고 싶다면 아래와 같이 구현하면 된다.

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

A < B이더라도 자연스럽게 스왑이 되며, 시간 복잡도는 O(logN)이 나오게 된다.

최소 공배수 구현

최소 공배수는 위에 구현해둔 함수를 이용하면 된다.

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

Reference

• devLulu.log
• 위키백과