최대공약수 최대공배수

function solution(n, m) {
    let gcd = 1;
    let lcm = 0;
    const answer = [];

    for (let i = 1; i <= Math.max(n, m); i++) {
        if (n % i === 0 && m % i === 0) {
            gcd = i;
        }
    }

    lcm = (n * m) / gcd;

    answer.push(gcd);
    answer.push(lcm);

    return answer;
}

 

풀이를 위해 유클리드 호재법을 이용했습니다.

 

유클리드 호제법의 원리는 두 수를 나눈 나머지를 r이라고 할 때, 두 수 중 작은 수와 r의 최대공약수가 두 수의 최대공약수와 같다는 것이다. 이러한 과정을 반복하다가 나머지가 0이 될 때 나누는 수가 두 수의 최대공약수인 것입니다.

 

위를 활용하여 

최대 공약수는 1부터 N(a, b 중 작은 수)까지 순회하면서 a와 b를 각각 나누었을 때 그 나머지가 둘 다 0이되는 수, 즉 나누어 떨어지는 수를 찾고

최소 공배수는 두 수를 곱한 값을 최대공약수로 나눈 수임을 활용하여 풀이했습니다.