LCM(최소공배수), GCD( 최대공약수)

• 약수: 어떤 수를 나누어떨어지게 하는 수
• 배수: 어떤 수의 1, 2, 3, ...n 배하여 얻는 수
• 공약수: 둘 이상의 수의 공통인 약수
• 공배수: 둘 이상의 수의 공통인 배수
• 최대 공약수(GCD. Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수
• 최소 공배수(LCM. Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수

 

최대공약수를 유클리드 호제법을 이용해서 구해보자.

const GCD = (a, b) => {
  let r = a % b;
  if (r === 0) return b;
  return GCD(b, r);
}
GCD(160, 16) // 16

function gcd(m, n) {
  if (m % n === 0) return n;
  return gcd(n, m % n);
}
gcd(16, 24) // 8

매개변수를 넣는 순서는 상관없다. 큰 수로 작은 수를 나누면 나머지는 작은 수가 그대로 나오기 때문에 저절로 큰 수에서 작은 수를 나누게 된다. 

 

function gcd(m, n) {
  if (m % n === 0) return n;
  return gcd(n, m % n);
}
let GCD = gcd(16, 24)

let LCM = 16 * 24 / GCD // 48​

최소 공배수는 두 수를 곱한 후에 GCD로 나누면 구할 수 있다. 

 

 

약수를 O(log n)으로 구하는 방법

let num = 36;
//num의 제곱근을 구해준다
let sqrt = Math.floor(Math.sqrt(num)) //6
let divisor = []
for(let i = 1; i <= sqrt; i++){
  if(num % i === 0){
  //제곱근 이후에 있는 약수는 num 에서 해당 약수를 나눠주면 구할 수 있다.
    divisor.push(i, num / i)
  }
}
//중복을 제거하고 정렬을 해주면
divisor = [...new Set(divisor)]
divisor.sort((a, b) => a - b) //[ 1, 2, 3, 4, 6, 9, 12, 18, 36 ]