[JS] 합성수 찾기

ㄴ문제를 보고 1~n까지의 수중에서 소수의 개수를 구한 후, 이를 빼면 어떨가란 생각을 했다.

 

에라토스테네스의 체 방식이 떠올라서 해당 방식으로 소수의 개수를 구한 후, 전체에서 빼 주었다.

 

배열을 2부터 n까지 잡기도 했고 n이 3이하면 답이 0이므로 이를 예외처리해주었다.

 

 

 

에라토스테네츠의 체로 소수 개수 구하기

 

function solution(n) {
    if (n<4)  return 0
    
    let lst = new Array(n-1).fill().map((v,i) => i+2)
    let cnt = 0
    
    while (lst.length > 0) {
        const tmp = lst.shift();
        cnt ++;        
        lst = lst.filter((el) => el%tmp !==0 )
        
    }
    
    
    
    console.log(cnt)
    return n- cnt -1;
}