JavaScript 최소공배수 구하기

문제

자연수로 이루어진 배열 arr이 입력되었을 때
arr 안에 있는 모든 자연수의 최소공배수를 구하는 함수 solution을 완성해보겠습니다.

용어 및 개념

코드에 활용되는 용어와 개념을 간단하게 알아보겠습니다.

유클리드 호제법

a > b 를 만족하는 두 자연수 a와 b가 있을 때 a % b = r 이라고 하자.
만약 r != 0 이라면, 이번에는 b % r = r' 이라고 하자.

위와 같은 과정을 반복했을 때
x % y = 0을 만족하는 x와 y가 존재한다면
y는 두 자연수 a와 b의 최대공약수가 된다.

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

두 수 a와 b의 최소공배수를 LCM, 최대공약수를 GCD라고 했을 때
LCM = a * b / GCD 를 만족한다.

풀이

위에서 확인한 개념을 코드로 구현해보겠습니다.

function solution(arr) {
    const getGCD = (a,b) => a % b === 0 ? b : getGCD(b, a % b);
    const getLCM = (a,b) => a * b / getGCD(a,b);
    return arr.reduce(getLCM)
}

Reference
유클리드 호제법 | 네이버 지식백과
호제법 | 네이버 국어사전
최대공약수와 최소공배수의 관계 | 수학방
N개의 최소공배수 | programmers