[JavaScript] 소수 찾기

level : 1

문제 링크 : 소수 찾기

프로그래머스

My Solution

function solution(n) {
    let answer = 0;
    let prime = new Array(n+1).fill(true);
    for(let i = 2; i <= n; i++){
        if(prime[i]){
            answer++;
            for(let j = 2*i; j <= n; j+=i)
                prime[j] = false;
        }
    }
    return answer;
}

풀이방법
소수 구하는 방법 중  에라토스테네스의 체를 이용하였다.

prime이라는 크기가 n+1인 Array에 모두 true로 채웠다.

2이상의 수만 범위에 들어오기에 반복문을 2부터 시작한다.

index의 숫자가 소수라면 answer를 1 증가시키고 index의 배수를 인덱스로 가지느는 prime의 값을 모두 false로 바꾼다.
반복문이 종료되면 answer를 반환한다.

느낀점

에라토스테네의 체가 아닌 Set을 이용하여 간단하게 풀었다가 시간초과가 발생했다.시간복잡도를 고려하며 코드를 작성해야겠다.