[종만북] 에라토스테네스의 체를 비트마스크로 구현 방법

 

에라토스테네스의 체는 굉장히 빠르게 동작하는 소수 찾기 알고리즘입니다.

 

알고리즘에 대해 간단히 요약을 하자면

소수를 구할 때 소수가 아닌 수들의 배수는 소수가 아니기 때문에

그들을 모두 지워나가면서 남은 수(소수) 들을 찾는 방법인데,

수의 범위가 점점 커지면, 메모리 공간이 부족하기 때문에 이를 극복하기 위해 비트 마스크를 이용합니다.

(기존 알고리즘 또한 웬만한 범위 내에서는 잘 작동합니다)

 

따라서 비트마스크를 사용하는 구간도 메모리 영역에 국한되는데,

 

기존 에라토스테네스의 체 구현 과정에서 bool 배열로 범위 내 소수가 아닌 수들의 인덱스를 모두 false 처리하고, 소수들을 true 처리해서 소수들을 골라냈다면

 

이번엔 비트마스크를 이용해서, check 역할을 하는 배열을 unsigned char (0 ~ 255, 8 bits) 배열로 선언한 후,

어떤 수가 소수인지 확인하는 방법입니다.

 

배열을 이용하는 방법

• 우선, 문제에서 주어진 수들의 최대 범위를 MAX_N이라는 const 변수로 선언합니다.
• 배열 선언 시, unsigned char 배열이 8 bits 이기 때문에, 배열의 크기도 MAX_N / 8로 선언해야 합니다.
• 따라서, unsigned char 배열은 기존 bool 배열에 비해 한 원소당 체크할 수 있는 수가 8배 많습니다.

잠깐 예시를 들어보자면,

기존 bool 배열에서 0~7의 수들이 소수가 아닌지 표현하려면, 각각에 대해 on/off (true/false)를 체크하는 반면,

unsigned char 배열은 8비트(0~255)의 수 하나만을 이용해 on/off를 체크할 수 있습니다.

 

ex) 255 = 11111111 -> 0~7 모든 수가 on

 

그렇다면 남은 것은 이제 어떤 수 k가 소수인지 확인하는 방법과, 소수가 아니라고 표시하는 방법(스위치를 off)이 필요합니다.

 

 

1. 소수인지 확인하는 방법

 

비트 마스크를 아시는 분들이라면 어렵지 않은 방법입니다.

 

• 어떤 수 k에 대해서 8로 나눈 수(오른쪽으로 3비트 시프트)와 (배열 각 원소들이 8배 축소되었기 때문에)
• k를 7과 AND 연산 (단위가 8로 확대되었기 때문에 7로 AND 연산을 하면 8로 나눈 나머지를 구할 수 있게 됩니다)

 

위의 두 식이 true라면 배열에 k에 해당하는 수가 들어있는 것이고, false 라면 없는 것이므로 소수가 아닙니다.

 

간단히 설명하자면, 우리가 구하는 k가 소수인지 확인하려면 k 자체는 정수지만

우리가 선언한 배열 원소 하나하나가 8개의 정수들을 기록하기 때문에 k가 소수인지 구하려면 k를 8로 나누고, 그 나머지를 확인해봐야 합니다.

 

참고로, 소수 확인 배열은 미리 memset으로 모두 255(모두 true)로 선언해 놓은 상태입니다.

 

2. 소수가 아니라고 표시하는 방법

위 방법도 에라토스테네스의 체 구현에서 아주 중요한 역할을 하는데,

알고리즘 자체가 소수가 아닌 수들을 이용해서 소수 판정을 하기 때문입니다.

 

방법은 1번과 거의 비슷한데,

1번에서 설명한 두 식을 비트 연산을 이용해 "제거" 하면 됩니다.

 

우리가 어떤 비트 연산을 이용해 A 비트에 대한 원소의 삭제를 하려면

비트 연산에서는 A &= ~(1 << p) (p는 양수)를 합니다.

~(1<<p)를 하면 p 인덱스에 있는 비트만 꺼지고 나머지는 모두 켜지기 때문에

& 연산을 하면 반드시 A 비트에 있는 p 인덱스의 비트는 꺼지게 되고 나머지는 그대로 유지됩니다.

 

에라토스테네스의 체에서도 마찬가지로 어떤 수 k가 소수가 아님을 표시하기 위해서는

 

우선 k를 8로 나눈 것에다가 k를 8로 나눈 나머지의 원소를 삭제하면 됩니다.

 

식으로 나타내자면

prime [k>>3] &= ~(1 << (k&7))으로 표현 가능합니다.

 

위 두 방식을 이용하면, 기존 에라토스테네스의 체 코드를 비트 마스크로 바꿀 수 있습니다.

 

예시

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

가장 간단한 소수 구하는 문제입니다.

 

1. 기본 에라토스테네스의 체 코드

#include <iostream>
using namespace std;
 
bool ans_prime(int n) {
    if (n == 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
int main()
{
    int m,n;
    cin >> m >> n;
 
    for (int i = m; i <= n; i++) {
        bool k = ans_prime(i);
        if (k == true) cout << i<<"\n";
    }
}

 

2. 비트 마스크를 이용한 에라토스테네스의 체 코드

#define MAX_N 1000000
#include <iostream>
#include <math.h>
#include <cstring>
using namespace std;
 
unsigned char sieve[(MAX_N + 7) / 8];
//k가 소수인지 확인
inline bool isPrime(int k) {
    return sieve[k >> 3] & (1 << (k & 7));
}
//k가 소수가 아니라고 표시
inline void setComposite(int k) {
    sieve[k >> 3] &= ~(1 << (k & 7));
}
//비트마스크 에라토스테네스의 체
//함수수행 후 isPrime()을 통해 소수인지 아닌지 확인 가능
void eratosthenes() {
    memset(sieve, 255, sizeof(sieve));
    setComposite(0);
    setComposite(1);
    int sqrtn = int(sqrt(MAX_N));
    for (int i = 2; i <= sqrtn; ++i)
        if (isPrime(i))
            for (int j = i * i; j <= MAX_N; j += i)
                setComposite(j);
}
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    eratosthenes();
    for (int i = a; i <= b; i++) {
        if (isPrime(i)) {
            printf("%d\n", i);
        }
    }
    return 0;
}

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~