글이 다소 말이 험해지는 거 같아서 설명 하나만 드립니다.
에라토스테네스의 체는 매 쿼리마다 전체를 한 번씩 계산하라고 있는 알고리즘이 아니고, 전체적으로 한 번 계산한 뒤에 여러 번 재사용하는 알고리즘입니다. 다만, 소수의 개수는 $O(n)$보다 작은 $O(\frac{n}{\log n})$이기에, 이 문제를 해결하는 시간 복잡도의 주요한 차이는 이 부분에서 크게 발생합니다.
에라토스테네스의 체의 시간복잡도는 $O(n \log \log n)$입니다. 일반적으로 $n=10^7$이 되더라도 100~200ms 내에 잘 돌아가는 알고리즘이 에라토스테네스의 체입니다. $n=10^6$인 경우에 에라토스테네스의 체를 사용했다고 시간 초과가 발생하는 일은 코드를 작정하고 구데기같이 짜지 않는 이상 웬만하면 일어나지 않습니다.

azaka9541 3년 전 1
1000000 까지 정확하게 맞추는 걸로 봐서 정확하게 구현한 것 같음.
소수 찾기에서 이 문제로 고생하고 있다면, 아마 소수를 구하는데 1000000까지 주었다고 덥석 에라토스 테네스체 알고리즘 구현해서
for문 돌아가다 시간초과 나서 고민하는 백수들일꺼임.
확실히 테이블 만들어 놓고 구하는게 빠르긴 한데, 그 테이블을 빠르게 구할 방법은 여러번 for 문 돌면서 소수인지 쳐내는게 아니라
한번에 돌아야함.
아래의 소스는 filter 한방으로 1000000까지 소수 테이블을 구할 수 있음