수학 알고리즘 - 최소 공배수(LCM) 알고리즘

최소 공백수란

최소 공백수는 두 개 이상의 정수를 나누어 떨어지게 하는 가장 작은 양의 정수를 말합니다.

예를 들어 6와 8의 최소 공배수는 24입니다.

 

최소 공백수 알고리즘

1. 서로소 x 최대 공약수 = 최소 공백수가 나옵니다.
2. (두 개의 정수 곱) / 최대 공약수 = 최소 공백수가 나옵니다.

 

유클리드 호제법을 이용한 최소 공백수 코드 예시

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

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