최대공약수와 최소공배수(유클리드 호제법)

프로그래머스 레벨2 N개의 최소공배수를 풀이하지 못하여 찾아보니 레벨1의 최대공약수와 최소공배수를 이해해야 한다고 하여 다시 복습하기 위하여 기록한다.

프로그래머스 레벨 1 - 최대공약수와 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12940

풀이 방법

function solution(n, m) {
    let a = m; // 큰 수
    let b = n; // 작은 수
    let r = 0; // 큰 수를 작은 수로 나눴을 때의 나머지 값
    
    // 몇 번 반복해야할지 모를 때에는 while문 사용
    while( a % b > 0 ) { // a를 b로 나눈 나머지값이 0보다 클때까지 반복문을 돌린다.
        r = a % b // 큰 수에서 작은 수를 나눈 나머지 값을 저장
        a = b; // 큰 수를 나눴을 때의 작은 수를 가져온다.
        b = r; // 작은 수에는 나머지 값을 가져온다.
    }
    
    // 최소공배수는 두 수를 곱한 수에 최대공약수를 나눠준 몫의 값. n*m/b
    return [b, (n*m)/b]
}

유클리드 호제법이란?

• 최대공약수를 구하기 위한 알고리즘 공식이다.
• a를 b로 나누었을 때 (a가 b보다 클 경우), 즉 큰 수를 작은 수로 나누었을 때 나머지 값이 0이 되면 작은 수(b)가 최대공약수가 되는 공식이다.
• 나머지 값이 0이 되지 않으면, 작은 수(b)가 큰 수(a)가 되고, 나머지 값이 작은 수(b)가 된다.
• 반복했을 때에 나머지 값이 0이 나오면, 작은 수(b)가 최대공약수가 된다.

해당 문제는 while문을 활용하여, 큰 수를 작은 수로 나누었을 때 나머지 값이 0보다 클때까지 나머지 값(r)을 큰 수에서 작은 수를 나눈 값을 저장하고, 큰 수는 작은 수로 재할당하고, 작은 수는 나머지값으로 재할당한다.

이 반복문이 종료되었을 때 나온 b, 나머지값이 최대공약수가 된다.

최소공배수는 두 수를 곱한 수에 최대공약수를 나눠준 몫의 값이 된다.