에라토스테네스의 체 최적화(optimized sieve of eratosthenes)

보통 에라토스테네스의 체를 구현할 때면

1. $i$ 루프( 소수 확인 루프 )를 최대 $N$ 까지 돈다.
2. $j$ 루프( $i$ 배수 루프 )를 $2\cdot i$ 부터 시작한다.

위와 같이 구현하는데

최적화 시

1. $i$ 루프를 $\sqrt N$ 까지 돈다.
2. $j$ 루프를 $i^2$ 부터 시작한다.

와 같다.

1번은 합성수 $N$의 약수를 $A\cdot B$ 라고 할 때

$A,B$ 중 어느 하나는 $\sqrt N$ 이하

어느 하나는 $\sqrt N$ 이상 이기 때문에

$\sqrt N$ 까지만 확인해주면 된다.

2번은 이미 전 루프들에서 $i^2$ 전에 있는 배수들을 다 확인했기 때문에

$i^2$ 에서 루프를 시작한다.

코드는 다음과 같다.

void do_sieve(int n){
   int t=sqrt(n);
   for(int i=2;i<=t;i++){
      if(sieve[i]) continue;
      for(int j=i*i;j<=n;j+=i) sieve[j]=1;
   }
}