[JS] N개의 최소공배수

yoon·2022년 10월 18일

코딩테스트

목록 보기
5/8

n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

function solution(arr) {
    let answer = arr[0]
    let element = arr.slice(1)
        
    while (element.length > 0) {
        let num = element[0]
        let makeDivisor = (n) => {
            let output = []
            for (let i = n; i > 0; i--) if (n % i === 0) output.push(i)
            return output
        }
        let divisor = makeDivisor(Math.min(answer, num))
        let gcd = divisor.find(item => Math.max(answer, num) % item === 0)
        answer = answer * num / gcd
        element.splice(0, 1)
    }
    
    return answer;
}

최소공배수를 구하는 공식만 알면 된다. 최소공배수는 구하고자하는 두 수의 곱 / 두 수의 최대공약수이다.
공식화하면 LCM(a, b) = (a * b) / GCD(a, b) 이다.
두 수 이상의 최소공배수를 구하는 방법은 위의 공식을 계속 반복해주면 된다.
LCM(a, b, c) = (LCM(a, b), c) 이다.

profile
얼레벌레 개발자

0개의 댓글