티스토리 뷰

Table of Contents


개요

단순한 방법

최적화

문제




1. 개요


 프로그래밍 문제를 해결하다 보면 소수를 활용해야 하는 경우가 종종 발생하는데, 그 중에서도 특정한 값 N 이하의 소수를 모두 찾아야 하는 경우가 꽤 많습니다. 그럴 때 초,중학교 수학 시절 노가다 취급했던 에라토스테네스의 체가 꽤 좋은 방법이 되어줍니다. (여기에서의 소수는 양의 약수가 1과 자기 자신뿐인, 1보다 큰 자연수를 의미합니다.)




2. 단순한 방법


 에라토스테네스의 체를 잊으신 분들을 위해, 그 방법을 그대로 적용한 알고리즘을 소개해 드리면 다음과 같이 됩니다.


----------------------------------------------------------------------------------------------


 (0) 초기에는 2 이상의 모든 수가 체크되어 있지 않은 상태이다.


체크 상태 : 2, 3, 4, 5, 6, 7, 8, 9, 10


----------------------------------------------------------------------------------------------


 (1) 2 이상의 자연수 중 체크되지 않은 가장 작은 수를 찾는다. ( 찾은 수 : 2 )


 (2) 찾은 수는 소수 확정이다.


 (3) 찾은 소수의 배수들을 모두 체크한다. (4, 6, 8, 10, ... ) ( * 소수 2는 제외 )


체크 상태 :  2, 3, 4, 5, 6, 7, 8, 9, 10


----------------------------------------------------------------------------------------------


 (4) 찾은 소수보다 큰 수 중, 체크되지 않은 가장 작은 수를 찾는다. ( 찾은 수 : 3 )


 (5) 찾은 수는 소수 확정이다. ( * 3 미만의 소수 중 3 의 약수가 없기 때문. )


 (6) 찾은 소수의 배수들을 모두 체크한다. (6, 9, 12, ... ) ( * 소수 3는 제외 )


체크 상태 :  2, 3, 4, 5, 6, 7, 8, 910


----------------------------------------------------------------------------------------------


 (4) 찾은 소수보다 큰 수 중, 체크되지 않은 가장 작은 수를 찾는다. ( 찾은 수 : 5 )


 (5) 찾은 수는 소수 확정이다. ( * 5 미만의 소수 중 5 의 약수가 없기 때문. )


 (6) 찾은 소수의 배수들을 모두 체크한다. (10, 15, 20, ... ) ( * 소수 5는 제외 )


체크 상태 :  2, 3, 4, 5, 6, 7, 8910


 ...반복...


 (last) '체크 되지 않은 가장 작은 수' 가 N을 초과하면 끝.


 이처럼 (1)~(3)의 과정을 반복하면 N이하의 모든 소수를 찾을 수 있습니다. 'x가 2이상의 자연수일 때, x 미만의 소수 중 x의 약수가 없으면 x는 소수이다.' 라는 명제가 성립하기 때문이지요. 따라서 에라토스테네스의 체 알고리즘을 따라가면서 체크되지 않은 수들은 모두 소수가 되고, 모든 소수(N이하)는 체크되지 않음을 알 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
// code by RiKang, weeklyps.com
const int PN = 1000;
 
bool isprime[PN+5];
 
void primechk(){
    for(long long i=2; i<=PN; i++) isprime[i] = true;
    for(long long i=2; i<=PN; i++)
        if(isprime[i])
            for(long long j=i+1; j<=PN; j++)
                if(j%i==0)
                    isprime[j] = false;
}
cs


 에라토스테네스의 체를 있는 그대로 코딩한 함수입니다. primechk() 를 돌리고 나면 v가 소수인 경우에만 , isprime[v] = true 가 됨을 알 수 있습니다. 따라서 이 코드로도 소수를 구할 수 있습니다. 하지만 시간 복잡도가 O(N^2)이라는 점에서 좋은 프로그램이라고 보기는 힘듭니다. 




3. 최적화


 위의 단순한 방법을 최적화하기 위해선 먼저 j 가 돌아가는 반복문을 봐야 합니다. 잘 살펴보면 j 가 쓸데없이 i의 배수가 아닌 경우도 순회함을 알 수 있습니다. 다음과 같이 코드를 개선하면 j 가 i 의 배수인 경우만 순회하도록 할 수 있습니다. 초기값을 i+1이 아니라 2*i, 그리고 마지막 항을 j++가 아니라 j+=i 로 바꿔주는 것이지요.


1
2
3
4
5
6
7
8
9
10
11
12
13
// code by RiKang, weeklyps.com
const int PN = 1000000;
 
bool isprime[PN+5];
 
void primechk(){
    for(long long i=2; i<=PN; i++) isprime[i] = true;
    for(long long i=2; i<=PN; i++)
        if(isprime[i])
            for(long long j=2*i; j<=PN; j+=i)
                isprime[j] = false;
}
 
cs


사실 여기까지만 해도 단순한 방법에 비해서 굉장히 빠르긴 하지만, 더 개선할 여지가 없는 것은 아닙니다.


 j = (2*i) ~ (i * i - i) 인 구간은 순회할 필요가 없기 때문입니다.


2*i 는 2의 배수이므로 이미 체크 되어 있고,

3*i 는 3의 배수이므로 이미 체크 되어 있고,

...

i*i-i 는 (i-1)의 배수이므로 이미 체크 되어 있기 때문이지요.


 이를 이용해 다음과 같이 개선할 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
// code by RiKang, weeklyps.com
const int PN = 1000000;
 
bool isprime[PN+5];
 
void primechk(){
    for(long long i=2; i<=PN; i++) isprime[i] = true;
    for(long long i=2; i<=PN; i++)
        if(isprime[i])
            for(long long j=i*i; j<=PN; j+=i)
                isprime[j] = false;
}
cs

 

 여기까지 최적화를 마친 에라토스테네스의 체 알고리즘은 시간복잡도가 O(N log log N) 인 것으로 알려져 있으며, 이는 O(N log N)보다도 더 빠르기 때문에 단순한 방법에서 사용한 O(N^2)과는 많은 차이가 있습니다.




4. 문제


(0) [BOJ 1929] 소수 구하기


※ 본문의 코드들은 C++ 14 환경으로 작성되었습니다.