소수를 찾는 빠르고 쉬운 방법, 고대 수학자 에라토스테네스가 발견함

알고리즘

n의 소수를 구하고자 할 때,

1. 2부터 n까지의 모든 수를 나열한다.
2. 2는 소수이므로 남겨둔다.
3. 2를 제외한 2의 배수를 모두 지운다.
4. 남겨진 다음 수인 3은 소수이므로 남겨둔다.
5. 3을 제외한 3의 배수를 모두 지운다.
6. (다음 수인 4는 2의 배수이므로 3번 과정에서 삭제되었다.)
7. 남겨진 다음 수인 5는 소수이므로 남겨둔다.
8. 5를 제외한 5의 배수를 모두 지운다.
9. 위 과정을 반복하면 n까지의 모든 소수가 남게 된다.

Javscript 구현

function solution(n) {
    if (n < 2) return 0;
    
    const isPrime = Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    let count = 0;
    
    for (let i = 2; i * i <= n; i++) {
        if (!isPrime[i]) continue;
        for (let j = i * i; j <= n; j += i) {
            isPrime[j] = false;
        }
    }
    
    return isPrime.reduce((acc, val) => acc + (val ? 1 : 0), 0);
}

Something More...

어떤 수 n이 소수인지 판별하려면 그 제곱근까지 확인하면 충분하다.

• n이 120이라면, 11^2 > 120이므로 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.
• 11보다 큰 수에서 약수를 찾는다면, 그 약수에 곱해지는 수는 이미 11 이하에서 처리됐기 때문이다.
• 이 사실로 첫 번째 for문에서 제곱근까지 순회하는 이유를 이해할 수 있다.

어떤 수의 배수를 지울 때 그 수의 제곱부터 지워나가도 충분하다.

• 그보다 작은 배수들은 이미 이전 루프에서 제거됐기 때문이다.
• 예를 들어, 3의 배수를 지워나갈 때 i + i인 6은 2의 배수를 처리하는 과정에서 지워진다.

참고

• 위키백과:에라토스테네스의 체
• 나무위키:에라토스테네스의 체