Index

1.문제
2.내 코드

문제

자연수 n이 주어지면, 1과 n사이의 소수의 개수를 반환하시오.
예시)
입력:13
출력:6

1~13 사이의 소수는 2,3,5,7,11,13 총 6개이다.

내 코드

<script>
    function solution(n) {
        let prime = Array.from({length:n+1},()=>false);
        for(let i=2; i<=n;i++){
            if(!prime[i]){
                for(let j=i*2; j<=n;j +=i){
                    prime[j]= true;
                }
            }
        }
        for(let i=2;i<=n;i++){
            prime[i]= !prime[i];
        }
        return prime.filter(ele=> ele).length;
    }
    console.log(solution(13));
</script>

위 문제에서 중요한건, 효율성테스트를 통과하는 것이다.
반복문을 통해 1부터 n까지의 수를 순회하며, 모든 숫자에 대해 소수판별을하면 시간초과를 하게 된다.
따라서 위 코드는 에라토스테네스의 체 방법을 이용한다.

설명

(1). 자연수 n의 소수판별을 할 때, 2부터 루트(n)까지의 수까지로만 나누어지는지 판별하면 자연수n이 소수인지아닌지를 알 수 있다.
**루트(n)은 k라 한다.

(2). 1부터 자연수 n까지의 모든 소수를 구할 때, 2~k까지의 모든 배수를 제거하고 남은 모든 수는 소수이다.

위 두가지를 동시에 적용하면 1~n까지의 모든 소수를 구할 수 있다.

아래 링크 참조
https://ko.wikipedia.org/wiki/에라토스테네스의_체