에라토스테네스의 채 - 소수 구하기

에라토스테네스의 채

 특정 범위의 소수를 판정하는데 유용한 알고리즘으로 만일 '1개의 수'가 소수인지를 판정하고 싶다면 다른 알고리즘을 사용하는게 더 좋습니다.

 기본적인 원리는 수학 시간에 많이 봤습니다. 일단 2를 제외한 배수들을 전부 지우고 그 다음은 3의 배수들, 4는 이미 지워졌으니 5의 배수를... 이런 식으로 수를 지워나가면 됩니다. 아래 위키백과의 사진을 탐고한다면 바로 이해할 수 있을 것입니다.

이미지 출처 : https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity

알고리즘으로서 에라토스테네스의 채

 백준 실버 문제부터 자주 등장하게 되며 소수를 판정하는 문제들에 자주 사용하게 됩니다. 특히 범위 내 소수를 구할 수 있다는 알고리즘에서 매력적이며 정말 간단하게 구현이 가능한 알고리즘입니다.

 에라토스테네스의 채 알고리즘의 시간복잡도는 O(nlog(logn))으로 꽤 빠른 편입니다.

 

에라토스테네스의 채 C++ 코드

    for(int i = 2; i <= end; i++)
        for(int j = 2; i*j <= end; j++)
            prime[i*j] = -1;

 일단 가장 기초적인 코드입니다. 위 알고리즘을 그대로 말로 옮긴 형태로 i가 증가하면서 i의 배수들을 전부 지우게 됩니다(prime[i*j] = -1). 그런데 위 시간복잡도를 조금 생각해보면 O(nlogn)에 가깝게 나올 것 같습니다. 그 이유는 한번 -1로 걸러진 수를 또 탐색한다는 이야기입니다.

 예를 들면 4의 경우 i = 2일때 이미 걸러진 수이며 4의 배수는 2의 배수이기도 합니다. 그런데 위 코드에서는 굳이 4의 배수를 한번 찾아다니는 수고를 들이고 있기 때문에 쓸데없는 과정이 들어가 있다고 볼 수 있습니다.

    for(int i = 2; i*i < 1000; i++){
    	if(prime[i]){
        	for(int j = i*i; j < 1000; j += i)
            		prime[j] = false;
    	}
    }   

 그래서 변형된 코드가 위와 같습니다. 위와 다르게 처음 배열을 true로 초기화 한 다음(논리상 편하게 하기 위함으로 안해도 무방) 코드를 실행하면 됩니다. 왜 j = i * i가 되냐고 하면 예를 들어 5의 경우 10, 15, 20의 경우 이전의 2, 3, 4를 탐색하면서 이미 지워졌기 때문에 이를 이용해 i * 2 ~ i (i - 1) 탐색을 생략한겁니다.

 

참고하면 좋은 사이트

- 에라토스테네스의 채 한국어 위키백과

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

- 풀어보면 좋은 문제 둘

1978번: 소수 찾기

 

1929번: 소수 구하기