비트 마스킹을 이용한 소수 찾기 (에라토스테네스의 체)

이 글은 `알고리즘 문제해결전략 - 구종만 (인사이트)의 내용을 일부 참고하여 작성하였습니다.

---

 

에라토스테네스의 체를 이용한 소수 찾기 기법은 2 부터 시작해 해당 값이 소수이면, 그 값의 배수를 숫자가 있는 풀(pool)에서 지워나가는 방법을 이용해 풀에 소수만 남기는 기법이다.

어떤 소수인 n에 대해서 n * i (i > 0)에 해당하는 값을 걸러내는 체를 이용한다.

 

위 방법에서 체에 대한 배열의 크기는 확인하려는 값의 최댓값이 될 것이다. 만약 1억까지의 수를 확인하려고 하면 boolean 타입의 배열을 써도 1억 바이트나 사용해야 한다는 것이다.

 

사실 0과 1만을 표현하는데 있어서 가장 좋은 데이터는 비트이다. 

하지만 보통 프로그램 언어에서는 true/false를 표현하는데 사용되는 boolean 타입까지도 1바이트나 이용한다. 직접적으로 bit와 관련된 primitive 타입이 없다. (안정성 및 가독성 등의 문제로 bit 단위로 직접 조작하는 타입은 없다.)

 

따라서 표현은 unsigned char 이나 unsigned int로 하되, 이를 컨트롤 할 때는 bit 연산자를 이용하면 기존의 boolean 타입(1 byte)을 이용해 체를 구현했을 때보다 8배(1 byte = 8 bits)나 적은 데이터로 체를 구현할 수 있을 것이다.

---

핵심은 다음과 같다.

 

unsigned char를 이용할 것인데, unsigned char은 숫자를 표현하는데 있어서 부호비트가 없으므로 8 비트를 온전히 다 사용할 수 있다. (마찬가지로 unsigned int 등의 값도 이용할 수 있을 것이다.)

 

전부 1로 표시하여 (전부 소수로 표시) 체를 초기화 시킨다. 이후에 반복문을 돌면서 소수가 아닌 값들을 0으로 표시하면 된다.

비트 연산자를 이용해 직접적으로 1로 초기화 시키는 방법대신 우리는 unsigned char이 숫자를 표현하는데 8비트를 사용한다는 것을 알고 있으므로 0b1111'1111(2)를 넣어주면 될 것이다. (해당 값은 255이다.)

memset(sieve, 0b11111111, sizeof(sieve));

 

 

확인하려는 값 k에 대해 k에 대한 소수 여부가 sieve 배열의 어느 index에 있는지를 확인하려면, 간단하게 8로 나누면 될 것이다. 그리고 그 나머지가 해당 8bit에서 몇 번째에 k에 대한 bit 값을 가리킨다.

 

ex)

k = 20

k / 8 = 2 => sieve[2]에 k=20이 소수인지에 대한 비트가 있다.

이제 k에 대한 bit 위치를 알았으니, k가 소수가 아닌 경우, 해당 bit를 0으로 바꾸면 될 것이다.

이 말은 곧 sieve라는 집합에서 n (k%8)를 뺀다는 말과 동일하다.

 

- set에서 n 제거하기: set & ~(1<<n)

- sieve에서 k를 0으로 표시하기: sieve[k/8] & ~(1<<(k%8))

 

마지막으로 해당 비트가 0인지 1인지 확인하면 된다.

이것 또한 교집합을 이용해 쉽게 구할 수 있다.

k에 대해 k에 대한 비트만이 1로 체크되어 있는 집합을 A라고 할 때,

 

sieve[k/8] & A  의 결과가 공집합(0)이라면 해당 비트가 0이라는 의미가되고 그렇지 않다면 1이라는 의미가 된다.

 

추가적으로 비트 연산자를 이용해 위 식을 표현하면...

k/8 => k >> 3 (8 = 2^3)

k%8 => k&7

---

위에서 구한 식을 이용해 코드를 구현한다면,

 

using namespace std;

constexpr int MAX = 1'000'000;

unsigned char sieve[(MAX + 7) / 8];

inline bool isPrime(const int k)
{
    return sieve[k>>3] & (1 << (k&7));
}

inline void setComposite(const int k)
{
    sieve[k>>3] &= ~(1 << (k&7));
}

void eratosthenes(const int n)
{
    memset(sieve, 0b11111111, sizeof(sieve));
    sieve[0] = 0b11111100; // set 0 and 1 to 0(not prime number)

    int sqrtn = static_cast<int>(sqrt(n));
    for(int i=2; i<=sqrtn; ++i)
    {
        if (isPrime(i))
        {
            for(int j=i*i; j<=n; j+=i)
            {
                setComposite(j);
            }
        }
    }
}

Note: sieve 배열을 eratosthenes 함수를 이용해 만들고 반환하는 코드를 작성하면 'double free' 에러가 나타날 수 있다. 따라서 숫자가 커지만 heap에 배열을 선언하도록 하자! (전역변수로!)

 

Note2: C/C++에서는 조건문에서 0이 아닌 값을 true로 생각한다는 것을 기억하자

---

sieve를 초기화 시에 아예 짝수를 제외해버릴 수도 있다.

memset(sieve, 0b10101010, sizeof(sieve));

 

또한, 메모리를 더 줄이고 싶다면 짝수를 아예 처음부터 제외하여 배열에 넣지 않아도 될 것이다. 그렇다면 boolean을 사용했을 때보다 16배나 적게 사용된다.