[비트 연산]에라토스테스 체

소수를 구하는 에라토스테스 체를, 비트단위로 저장하면, 메모리를 절약할 수 있다. (1/8로 줄어듬)

즉, 각 숫자 단위로 한 개의 bool 값을 지정하는 것이 아니고, 비트 1개를 써서 합성수인지 소수인지 가리키게 하는 것.

1바이트면 8비트이기에 8개의 수에 대해 지정 가능.(1~8)

따라서, int로 나타낼 수 있는 2³²-1 까지의 값에 대해서 각각 소수여부를 지정하려면, 512MB 메모리 필요. (각 값에 대해 1바이트 사용하면 4GB 필요)

코드

const int MAX_N = 70000000;

unsigned char seieve[(MAX_N + 7) / 8]; //MAX_N의 1/8 만큼의 배열 확보

inline int isPrime(int n){

         return seieve[n >> 3] & (1 << (n & 7));  //소수이면 0을, 아니면 0보다 큰 자연수 리턴

}

 

inline void setComposite(int n){

         seieve[n >> 3] &= ~(1 << (n & 7)); //해당 위치의 비트를 0으로 세팅

}

 

void eratosthenes(void){  

         memset(seieve, 255, sizeof(seieve));

 

         setComposite(0);

         setComposite(1);

         int rootN = int(sqrt(MAX_N));

         for (int i = 2; i <= rootN; ++i){ //sqrt(MAX_N)까지만 하면 됨

                  if (isPrime(i)){

                           for (int j = (i * i); j < MAX_N; j+=i)  //i*i 부터 시작하면 됨. 더 작은 값은, 이미 그 전값에 의해 체크됨

                                   setComposite(j);                           

                  }

         }

}

Reference

1. 구종만. 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략. 인사이트. 

-끝-