소수 찾기

#나의 풀이

function solution(n) {
    let answer = 0;
    for (let i = 2; i <= n; i++){
        if(i === 2 || i === 3){
            answer++;
        }
        if(i % 2 !== 0){
            let j = Math.floor(Math.sqrt(i)) + 1;
            let s = 3;
            while(s <= j){
                if(i % s === 0){
                    break;
                }
                s += 2;
                if(s > j){
                    answer++;
                }
            }
        }
    }
    return answer;
}

 

#다른 방법

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;
}

*개수를 구하는 문제이기 때문에 개인적으로 굳이 set을 사용할 필요는 없다고 생각한다.

*이번 문제에서 가장 어려웠던 점은 소수에 대한 수학적 상식이었던 것 같다. 

*소수인지 아닌지를 검사할 때에 해당 미지수의 제곱근 이하의 숫자까지만 체크해보면 알 수 있다.