최대공약수와 최대공배수 자바스크립트

HyosikPark·2020년 11월 17일
0

알고리즘

목록 보기
21/72
나의 코드
function solution(n, m) {
    
    let nDivisor = [];
    let mDivisor = [];
    let commonDivisor = [];
    let answer = [];
    
    for(let i = 1; i <=n; i++) {
        if(n%i === 0) nDivisor.push(i)
    }
    
    for(let i = 1; i <=m; i++) {
        if(m%i === 0) mDivisor.push(i)
    }
    
    for(let i = 0; i <=mDivisor.length; i++) {
        if(nDivisor.includes(mDivisor[i])) commonDivisor.push(mDivisor[i]);
    }
    
    let greatestCommonDivsor = Math.max(...commonDivisor)
    answer.push(greatestCommonDivsor);
    
    answer.push(n*m / greatestCommonDivsor)
    
    return answer
}

다른 사람 코드
function greatestCommonDivisor(a,b) {
    return a%b === 0 ? b : greatestCommonDivisor(b,a%b)
} 

function LeastCommonMultiple(a,b) {
    return a*b / greatestCommonDivisor(a,b); 
}

function solution(n,m) {
    return [greatestCommonDivisor(n,m),LeastCommonMultiple(n,m)]
}

재귀를 이용한 방식이 속도도 훨씬 빠르고 간결하다.

최대 공약수
유클리드 호제법으로 푼것인데 (a>b)일 때 a가 b로 나누어지면 b가 최대공약수
그렇지 않다면 나누어 떨어질 때 까지 b / a%b를 반복한다.
나누어 떨어지면 a%b가 최대 공약수가 된다.

최소 공배수
a*b/최대공약수

참고

https://medium.com/@wooder2050/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%99%80-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-javascript-a40121516de0

0개의 댓글