[알고리즘/C++] 에라토스테네스의 체

안녕하세요! 테크지니어22입니다.

오늘은 소수와 관련된 문제를 풀때 알아두면 유용한 에라토스테네스의 체를 알아보도록 하겠습니다.

 

 

[정의]

n이하의 모든 소수를 찾는 방법으로 마치 체로 치듯이 수를 걸러낸다하여 에라토스테네의 체라고 부릅니다.

시간복잡도는 O(Nlog(logN))

 

 

[방법]

1. 1을 지운다.

2. 2외의 2의 배수를 지운다.

3. 3외의 3의 배수를 지운다.

4. 남아있는 수 5 외의 5의 배수를 지운다. 

5. 남아있는 수 7 외의 7배의 배수를 지운다.

6. 남아 있는 수는 소수이므로 소수의 배수들 지우는 거 반복한다.

-> sqrt(n)이하까지 반복한다.

 

 

[왜 sqrt(n)이하까지 반복해야 하는 가?]

두 가지 정리가 필요하다.

정리1. 2이상의 정수 n의 소인수는 적어도 하나가 존재한다.

정리2. 양의 정수 n이 합성수면 n의 소인수 중에는 p <= sqrt(n)인 소인수 p가 존재한다.

(정리 2는 정리1로 증명할 수 있다.)

 

정리2 증명

 

 

n보다 작은 합성수는 sqrt(n)보다 작은 소수의 배수만 체크해도 전부 지워진다는 의미이다.

 

즉 n이하의 합성수들을 제거하기 위해서는

p<= sqrt(n)인 p이하의 소수의 배수들만 제거하면 된다. (i*2)

그런데 코드를 작성할 때 i*2가 아니라 i*i부터 처리하는 이유는 정리 2에 의해 i*i이전까지의 소수가 아닌 수들의 제거가 이미 처리되었기 때문이다.

 

 

[코드]

const int MXM = 400002 ;
vector<bool> seive(MXM,true);
vector<int> primes;

for(int i = 2 ; i*i <MXM ; i++) {
	if(!seive[i]) continue;
	for(int j = i*i ; j < MXM <j+=i){
    	seive[j] = false ; 
    }
    
   for(int i = 2 ; i < MXM ; i++) if(seive[i]) primes.push_back(i); 
}