[js] Programmers_Lv.0_소인수분해

문제

프로그래머스

자연수 n의 소인수를 담은 배열을 오름차순으로 반환하시오

 

아이디어

1. 에라토스테네스의 체를 이용하여 소수를 구하자.

2. n을 소수들로 나누어서 나누어지면 answer 배열에 추가한다 ( 한 번이라도 나누어진다 = 소인수)

 

구현(풀이)

function solution(n) {
    var sieve = []
    var answer = []

	// 1. 에라토스테너스의 체 구현
    for (var i=0; i< n+1; i++) {
             sieve.push(i)     
    }
    sieve[1] = 0 

    for (var i=2; i< n+1; i++) {
        for (var j=2; j< Math.ceil(n+1/2); j++) {
                if (sieve[i*j]) {
                    sieve[i*j] = 0
                } 
            }
    }

    var sieve = sieve.filter((element) => element !== 0 );

	// 2. 소인수 찾기
    for (var j =0; j< sieve.length; j++) {
        if ((n%sieve[j]) == 0) {
            answer.push(sieve[j])
        } 
    }


    return answer;
}

 

남의 풀이

function solution(n) {
    var answer = [];

    for(let i = 2; i <= n; i++) {

        while (n % i === 0) {

            n = n / i;
            answer.push(i);

        }
    }

    return [...new Set(answer)];
}

1. n을 2부터 n까지 각 수로 나눈다. 

  - 이 때, 나누어진다면 answer에 추가한다

3. set을 통해서 중복값을 제거하고 [...set]을 통해서 Array로 형변환을 해준다.

참고문서

- mdn, Math.sqrt() : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Math/sqrt

- mdn, Math,ceil() : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Math/ceil

- mdn, set : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Set

- mdn, spread syntax : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Operators/Spread_syntax

- mdn, new : https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Operators/new