에라토스테네스의 체 (Sieve of Eratosthenes)

에라토스테네스의 체는 가장 대표적인 소수 판별 알고리즘이다.

2부터 시작하여 2의 배수를 모두 삭제하고,
3의 배수를 모두 삭제,
(4는 2의 배수이므로 이미 삭제되었으므로), 그다음 5의 배수를 모두 삭제..
이렇게 배수들을 모두 제외시키면서 마지막에는 소수만 남게 되는 알고리즘이다.

코드

function solution(n) {
    const sieve = new Array(n + 1).fill(true);
    
    for (let i = 2; i <= n; i++) {
      	// 이미 지워진 숫자라면 무시한다.
        if (sieve[i] === false) continue; // e.g. i = 4 가 나온다면 이미 false 처리 되어있을 것이다.
        
        // 이미 지워진 숫자가 아니라면
        for (let j = i + i; j <= n; j += i) { // i의 배수들을 다 지워준다.
            sieve[j] = false;
        }
    }
    
    return sieve.filter((el) => el).length - 2;
}

풀이

1. 먼저 체에 거르기 전에 모든 숫자를 배열 안에 가지고 있어야한다.
   1부터 10 사이의 소수의 개수를 구한다고 가정한다면, 길이가 10인 배열을 true로 채워서 만들어야한다.
   이때, 배열은 index가 0부터 시작하기 때문에 +1 해줘야 한다.

[true, true, true, true, true, true, true, true, true, true, true]
   0    1     2     3     4     5     6     7     8     9     10      

2. 그러고나서 반복문을 순회할 건데, 2의 배수부터 삭제해줘야 하기 때문에 i는 2부터 시작한다.
   그리고 내부 반복문을 돌려 i의 배수를 모두 삭제해준다.

i = 2 일 때,
[true, true, true, true, false, true, false, true, false, true, false]
   0    1     2     3      4     5      6     7      8     9     10      

i = 4일 때,
  i가 이미 false이므로 continue

i = 3 일 때,
[true, true, true, true, false, true, false, true, false, false, false]
   0    1     2     3      4     5      6     7      8     9     10      

i = 5 일 때,
[true, true, true, true, false, true, false, true, false, false, false]
   0    1     2     3      4     5      6     7      8     9     10      

i = 7 일 때,
[true, true, true, true, false, true, false, true, false, false, false]
   0    1     2     3      4     5      6     7      8     9     10      

3. 반복문이 종료되면 (배수들이 체에 다 걸러지면) filter() 메소드를 이용해 값이 true인 요소들을 필터링하여 개수를 셀 수 있다.
   이때 주의해야할 점은 0과 1은 소수가 아니지만 배열에 포함되어있어 함께 카운팅되므로 -2를 해줘야 한다.

번외

배열을 true로 채우지 않고, 해당 숫자를 값으로 해서 소수 배열을 구할 수도 있다.

function solution(n) {
    const sieve = [];
    
    for (let k = 2; k <= n; k++) { // sieve[2] = 2; 이렇게 값 채움
        sieve[k] = k;
    }
    
    for (let i = 2; i <= n; i++) {
        if (sieve[i] === false) continue;
        
        for (let j = i + i; j <= n; j += i) {
            sieve[j] = false;
        }
    }
    
    return sieve.filter((el) => el).length;
}

이렇게 작성하면 n이 10일 때 sieve를 출력했을 때, 아래와 같은 배열을 얻을 수 있다.

[null, null, 2, 3, false, 5, false, 7, false, false, false]
   0    1    2  3    4    5   6     7    8      9     10      

더 간단한 코드

function solution(n) {
    const sieve = [false, false, ...Array(n - 1).fill(true)];
    
    for (let i = 2; i <= n; i++) {
        if (sieve[i]) {
            for (let j = i * 2; j <= n; j += i) { // sieve에서 i의 2의 배수부터 모든 배수를 모두 false 처리한다.
                sieve[j] = false;
            }
        }
    }
    return sieve.filter(Boolean).length; // false, 0, -0, 0n, "", null, undefined, NaN은 걸러진다.
}