소인수분해

소인수분해

소인수분해란, 어떤 수를 소수들의 곱으로 표현한 것이다. 예를 들어 12를 소인수 분해하면 2 x 2 x 3으로 나타난다.

중복을 제거하면 소인수는 2, 3이다.

 

소인수분해를 구하는 알고리즘을 공부해보았다.

function solution(n) {
    var answer = new Set();
    for (let i = 2; i <= n; i++) {
        if (n % i === 0) answer.add(i);
        while (n % i === 0) n /= i;
    }
    return [...answer].sort((a, b) => a - b);
}

1. 중복이 없어야하므로 Set으로 지정하였다.

2. n 나머지 i가 0일 경우 answer에 add 해준다.

3. n 을 낮은 숫자에서 나눌 수 있을만큼 나누어준다.

 

헷갈릴 수 있는 개념이지만, 익혀두면 좋을 거 같아 글로 정리해보았다.