에라스토테네스의 체

특정 범위 내에서 소수를 전부 구하고 싶을때 효율적인 방법은 에라토스테네스의 체이다.

 

O(N) 만큼의 Memory를 사용하여 O(Nlog(logN)) 만에 특정 범위 내의 소수를 전부 구할 수 있다.

 

에라스토테네스의 체를 구하는 Code

 

bool is_prime[1000005];

void sieve() {
	for(int i=2; i<=1000000; i++) is_prime[i]=true;
	for(int i=2; i<=1000000; i++) {
		if(is_prime[i]) {
			for(int j=i+i; j<=1000000; j+=i) is_prime[j]=false;
		}
	}
}