> 1부터 n까지의 범위에서 소수 목록을 구하는 알고리즘 > **소수 목록**이 필요하거나, **여러 번 소수 판별**을 해야 해서 **미리 전처리**해두면 좋은 경우에 유용하다. ## 핵심 아이디어 모든 수를 소수 후보로 두고, 어떤 수 k가 소수라면 k의 배수들은 합성수이므로 소수 후보에서 제외한다. ## 구현 ```javasript function eratosthenes(n) { const isPrime = Array.from({ length: n + 1 }).fill(true); isPrime[0] = false; isPrime[1] = false; for (let num = 2; num * num <= n; num++) { if (isPrime[num] === false) continue; for (let x = num * num; x <= n; x += num) { isPrime[x] = false; } } return isPrime.filter(Boolean); } ``` ## 구현 포인트 - 바깥 루프는 `num * num <= n` 까지만 돌린다. `num > √n`이면 `num * num > n` 이라서 배수의 시작점이 범위를 벗어난다. - 안쪽 루프는 `num * num` 부터 시작한다. `num * 2`, `num * 3`, ... `num * (num-1)`은 앞 (2..num-1) 단계에서 지워지기 때문에 추가로 확인할 필요 없음 ## 복잡도 - 시간: O(n log log n) - 공간: O(n) (`isPrime` 배열)