[Javascript] (프로그래머스 level 1) 소수 찾기

[Javascript] (프로그래머스 level 1) 소수 찾기

💡 구글에 Javascript 풀이가 많이 없거나, 배운 점이 있으면 포스팅합니다.

내 풀이

function solution(n) {
    const primeNums = new Array(n + 1).fill(true);

    for (let i = 2; i <= n; i++) {
        if (primeNums[i] === false) {
            continue;
        }
        for (let j = 2 * i; j <= n; j += i) {
            primeNums[j] = false;
        }
    }

    primeNums[0] = false;
    primeNums[1] = false;
    return primeNums.filter((bool) => bool === true).length;
}

• for문으로 나머지가 없는 수를 찾는 isPrime() 함수를 만들어서 이렇게도 해보고 저렇게도 해봤는데, 결국 효율성 테스트를 넘기려면 “에라토스테네스의 체”를 사용해야 하네요.
• 이리저리 해보다 안되서 검색으로 해결했습니다 😭 수학적인 문제에 약하네요.

다른 사람 풀이

function solution(n) {
    const s = new Set();
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2);
    for(let j=3; j<Math.sqrt(n); j++){
        if(s.has(j)){
             for(let k=j*2; k<=n; k+=j){    
                s.delete(k);
             }
        }
    }
    return s.size;
}

• 셋을 사용할거라곤 생각도 못했는데, 이렇게도 풀 수 있네요.