[JS] 최대공약수와 최소공배수

function solution(n, m) {
    var answer = [];
    let gcd = 1;
    for(let i = 2; i <= Math.min(n, m); i++) {
        if(n % i == 0 && m % i == 0) {
            gcd = i;
        }
    } answer = [gcd, n * m / gcd];
    return answer;
}

 

 

n과 m의 최대공약수(GCD), 최소공배수(LCM)

 

 

최대공약수(GCD) 찾기

 

`for` 루프는 `2`부터 `n`과 `m` 중 작은 값까지 반복

이는 `Math.min(n, m)`로 계산

반복문 내에서 `n`과 `m` 모두를 나눌 수 있는 `i`를 찾음

(`n % i == 0 && m % i == 0`)

만약 `i`가 `n`과 `m` 모두를 나눌 수 있다면, `gcd`를 `i`로 업데이트

이렇게 하면 `i`는 `n`과 `m`의 공약수 중 가장 큰 값

 

 

최소공배수(LCM) 계산:

 

최소공배수는 `n`과 `m`의 곱을 최대공약수로 나눈 값 (`n * m / gcd`)

 

 

 

---

 

 

 

다른 사람 풀이

 

 

 

유클리드 호제법을 이용한 GCD 계산:

 

`for` 루프는 조건 `r = a % b`가 참인 동안 반복

 

`a % b`는 `a`를 `b`로 나눈 나머지를 계산

`a % b`가 `0`이 될 때까지 반복

 

`a`는 `b`로 업데이트, `b`는 나머지 `r`로 업데이트

이 과정이 끝나면 `b`는 GCD를 갖게 됩니다.