문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 사항

n은 2이상 1000000이하의 자연수입니다.

입력

n : 10

출력

4

내가 했던 풀이 방법

1. n+1 크기의 boolean 배열을 만들고, 모든 요소를 true로 초기화해준다. (계산을 편하게 하기 위해 0번 인덱스를 사용하지 않으므로, n+1 크기로 선언한다.)
2. 0번, 1번 인덱스를 false로 바꿔준다. (0번은 사용하지 않고, 1번은 1은 소수가 아니라고 문제에서 주어졌기 때문에 false로 바꿔준다.)
3. 2번 인덱스부터 n까지 1씩 증가시키면서 해당 인덱스가 true일 경우, 해당 값은 소수로 판단하여 answer를 1 증가시켜준다.
4. n이하의 해당 값의 배수를 모두 false로 바꾸어준다.
5. 3-4번을 n번 인덱스까지 반복해준다.

코드

function solution(n) {
    var answer = 0;
    let prime = Array.from({length: n+1}, ()=>true);
    prime[0] = false;
    prime[1] = false;
    
    for(let i=2; i<=n; i++) {
        if(prime[i]) {
            answer++;
            for(let j=i*2; j<=n; j+=i) {
                prime[j] = false;
            }
        }
    }
    return answer;
}

회고

에라토스테네스의 체를 이용해서 문제를 풀이했다. 단순하게 2부터 해당 수 미만의 수에서 나누어지는 수가 없을 경우 소수로 판단했는데, 시간초과가 걸렸다. n의 수가 매우 큰 상황에서는 효율이 낮다는 걸 생각하지 못했다. (가끔씩 소수 문제를 풀 때 단순 풀이로만 해결해도 풀리는 경우가 많아서 효율좋은 알고리즘을 생각하지 못했다.) 효율이 가장 중요한데 그 부분을 조금씩 놓치고 있는 것 같아서 잘 하고 있는건지 가끔씩 걱정이 된다. 물론 테스트에서 효율이 극악이면 걸러지겠지만, 더 좋은 코드를 찾기 위해 좀 더 생각해보고 문제를 풀어볼 때가 되지 않았나 생각했다.