알고리즘 - 에라토스테네스의 체(C++)

 

최근 코딩테스트에서 소수를 판별해야하는 문제가 나왔다. 그래서 에라토스테네스의 체를 사용해야함을 바로 알았지만 아쉽게 떠올리지 못하여 정리해두려고 한다.

 

원래 소수를 판별하는 방법은 대학교 1학년 C언어 시간에 배울 정도로 쉽다. N까지 모두 나눠보며 나눠 떨어지는 수가 2이면 소수이다. 그러나 이것은 매우 시간이 오래걸린다. 

 

에라토스테네스의 체는 이 수가 소수인지 아닌지 판별하는 것이 아니라 1~100만 등 어떠한 범위내에서 소수인지 아닌지 판별할 때 유용하다. 즉 1~100만 중 소수가 몇개인가? 이러한 것을 해결하는 방법이다.

 

알고리즘은 다음과 같다.

 

1.  2 ~ N까지 2의 배수를 false 처리한다. 

2. 3 ~ N까지 3의 배수를 false 처리한다.

4. 5 ~ N까지 5의 배수를 false 처리한다.

5. 7~ N까지 7의 배수를 false 처리한다.

 

이러면 살아남은 true 숫자들이 소수가 된다! 증명은 하지 않는다. 난 수학과가 아니다. 그러나 직관적으로 나눠 떨어진다는 것은 소수가 아니라는 의미이기 때문에 납득못할 것은 아니다. 그러나 코드가 납득이 안될 수 있다.

 

int main(){   
        vector<bool> vec(300001, true);
        vec[1] = false;
        for(int i = 2; i * i < 300001; i++){
            if(vec[i]){
                for(int j = i * i; j < 300001; j += i) // i의 배수를 처리하기 위해서. 
                    vec[j] = false;        
            }
        }
  	}

 

이 코드는 1~30만의 숫자들 중 소수를 판별하는 에라토스테네스의 체를 사용한 코드이다. 여기서 이상한 점은 첫번째 반복문에서

i * i < N 이라는것이다!

 

숫자를 줄여 N이 13이라고 생각해보자 그렇다면 i가 4일때 반복이 멈추게될 것이다. 반복을 살펴보면

i = 2

-> 두번 째 반복문에서 j = 4 ~ 13까지 i의 배수들을 모두 false 처리한다. 4 6 8 10 12

 

i = 3

-> 두번 째 반복문에서 j = 9~ 13까지 i의 배수들을 모두 false 처리한다. 9 12

 

그렇다면 남은 숫자들은 2 3 5 7 11 소수만 남게 된다. 이미 i 보다 작은 숫자들은 모두 이전의 i 반복문이 처리될 때 소수 판별이 끝난 상태가 되기 때문에 신경쓸필요가 없다. 그리고 if(vec[i]) 에 의하여 지금 true 즉 소수인 녀석들만 위 반복을 돌기 때문에 쓸모없는 연산을 실행되지 않는다. 

 

마치 위의 코드가 알고리즘을 따르고 있지 않는 것 같지만 사실을 따르고 있다.

 

이 알고리즘의 시간복잡도는 O(Root(N))으로 웬만하면 모든 N에 대하여 사용할 수 있다.

 

하지만 문제를 풀다보면 결국은 이 숫자가 소수인지 판별해야하는 문제가 생긴다. 그 때는 에라토스테라를 조금 바꿔 이렇게 사용할 수 있다.

 

bool Era(int n){
	if(2 < n) return false;
    
    for (int i = 2; i * i <= n; i++){
    	if(n % i == 0) return false;
    }
    
    return true;
}

 

이렇게 하면 원래 O(N) 판별해야하는 것을 O(Root(N)) 으로 해결할 수 있다.