소수 찾기

출처

[프로그래머스] 소수 찾기

문제 설명

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

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

제한 조건

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

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #1

1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2

1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

문제 풀이

처음에는 그냥 단순하게 for문 돌려서 소수인지 아닌지 판별하고 카운트하는 방식으로 구현했다.
그런데 이렇게 하면 시간 초과가 난다.
이 문제는 효율성을 위해 에라토스테네스의 체 알고리즘을 사용해서 풀어야한다.

에라토스테네스의 체

소수는 1과 자기 자신으로만 나눠지는 수이다.
즉, 배수들은 소수가 아니다.

1은 소수가 아니니 제외하고,
2부터 시작하여 2의 배수, 3의 배수, ··· 이 배수들을 지워나가면 된다.
이 때, 2~n까지 반복문을 다 돌릴 필요 없이 n의 제곱근까지만 돌리면 된다.

소수를 판별할 때 N까지가 아닌 √n 까지 나눠보는 이유

function solution(n) {
   let arr = new Array(n + 1).fill(true);
    arr[0] = false;
    arr[1] = false;
    
    for (let i=2; i*i<=n; i++) {
        if (arr[i]) {
            /* i*i 이하의 배수들은 앞의 수의 배수들을 제거하면서
            이미 지워졌기 때문에 j=i*i부터 시작한다. */
            for (let j=i*i; j<=n; j+=i) {
                arr[j] = false;
            }
        }
    }
    return arr.filter(e => e === true).length;
}