[프로그래머스 JavaScript] 최대공약수와 최소공배수

🚩 프로그래머스 Level1 최대공약수와 최소공배수

 

 

function solution(n, m) {
    var answer = [];
    //유클리드 알고리즘 사용
    let a=n;
    let b=m;
    let tmp;

    //m이 더 큰경우 값 체인지
    if(n<m){
        [a,b] = [b,a]
    }

    while(b!= 0){
        tmp = a%b;
        a = b;
        b = tmp;
    }
    //최대공약수
    answer.push(a);
    //최소공배수
    answer.push(n*m/a);
    return answer;
}

코드 설명 : 최대 공약수를 구하는 방법으로 유클리드 호제법 알고리즘을 사용했다.

 

❓유클리드 호제법이란❓

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

 

ex) 1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어떨어진다.
• 따라서, 최대공약수는 21이다.

최소 공배수는 두 수의 곱 / 최대 공약수 이다.