[Algorithm] 최소공배수 구하기

최소공배수란 ?

공통된 배수중 가장 작은 값을 의미한다.
[ 12와 18의 최소 공배수 구하기 ]

12의 배수는 12, 24, 36, 48, 60, 72, ...
18의 배수는 18, 36, 54, 72, 90, 108, ...
공배수는 { 36, 72, 108, ... } 이고
공배수중 최솟값은 36 이다. (최대공배수는 무한대라 구하는게 의미없다.)

따라사, 최소공배수는 36이다.

최대공약수와 최소공배수의 관계

최대공약수와 최소공배수의 곱은 두 자연수의 곱과 같다.

예시

21과 30의 최대공약수와 최소공배수를 구하면,

21을 소인수 분해하면 3 * 7
30을 소인수 분해하면 2 * 3 * 5 

두 자연수의 최대공약수는 3,
최소 공배수는 2 * 3 * 5 * 7

21과 30의 곱 = (3 * 7) * (2 * 3 * 5) = 630
21과 30의 최대공약수와 최소공배수의 곱 
= 3 * (2 * 3 * 5 * 7) = 630

21과 30의 곱과 21과 30의 최대공약수와 최소공배수의 곱의 값이 같다.

How to

1. 유클리드 알고리즘을 사용해 최대공약수를 구한다.
   참고 : 유클리드-알고리즘-최대공약수-구하기

2. 두 수의 곱을 최대공약수로 나눠준 값이 최소공배수이다.

JavaScript 소스 코드

// 최대공약수 구하기
function gcd(a, b) { // 1번
  const remainder = a % b;  // 2번
  return remainder === 0 ? b : gcd(b, remainder); // 3번
}

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

유클리드 알고리즘을 통해 최대공약수만 구한다면 최소공배수 구하기는 어렵지 않다.