[BitMask] 에라토스테네스의 체

[BitMask] 에라토스테네스의 체

비트마스크를 이용한 에라토스테네스의 체 구현

에라토스테네스의 체는 빠르게 동작하기 때문에 수행 범위를 늘릴 때 부담이 되는 것은 시간보다는 메모리이다.

체를 구현 할 때 범위 내의 각 정수들의 소수 여부를 저장하기 위해 범위 만큼의 배열 크기를 선언해 두었어야 했는데 비트마스크를 이용하여 이를 줄일 수 있다.

이는 예를 들어 unsigned char로 배열을 잡을 경우 8bit를 사용하여 8개의 정수의 소수 여부를 1 or 0으로 표현, 이를 담은 하나의 정수로 저장하면 된다.

또한 type의 크기 이후 정수를 저장하려면 다음 배열에 다시 그 이후 8개의 정수 소수 여부를 한번에 저장한다.

prime[0] -> 0부터 7까지의 소수 여부 저장    : 10101100 (7 : 소수, 6 : no, 5 : 소수 ... )

prime[1] -> 8부터 15까지의 소수 여부 저장

따라서 하나의 메모리에 8개의 여부를 한번에 저장하기 때문에 평소 사용하던 메모리의 1/8로 줄일 수 있다.

#include <stdio.h>
#include <string.h>
#define MAX_N        100
 
int n;
// 배열 하나에 총 8개의 정보가 저장됨
// [0] = 000 -> 0부터 7까지 (10000000 7번째)    1byte = 8bit
unsigned char prime[(MAX_N + 7) / 8];
 
void print2(int num)
{
    int sh = 7;
    int flag = 0;
 
    for (; sh >= 0; sh--) {
        if ((num >> sh) & 1)    flag = 1;
        if (flag) {
            printf("%d", (num >> sh) & 1);
        }
    }
}
 
// k가 소수인지 판별
inline bool isPrime(int k)    {
    // 원소가 켜져있는지 판별
    // k >> 3    : k / 8과 같음 -> 8개 씩 정보를 저장하기 때문에
    // (1 << (k & 7)) -> 하위 7개의 bit만 판단
    return prime[k >> 3] & (1 << (k & 7));
}
 
// k가 소수가 아니라고 표시
inline void setComposite(int k)    {
    // 원소 삭제
    prime[k >> 3] &= ~(1 << (k & 7));
}
 
void eratosthenes() {
    memset(prime, 255, sizeof(prime));
 
    setComposite(0);
    setComposite(1);
 
    for (int i = 2; i * i <= n; i++) {
        if (isPrime(i)) {        // i 가 아직 소수이면
            for (int j = i * i; j <= n; j += i) { // i의 배수들을 false로
                setComposite(j);
            }
        }
    }
}
 
void printState(int num)
{
    print2(num);
    printf("\ti >> 3 : ");
    print2(num >> 3);
    printf("\ti & 7 : ");
    print2(num & 7);
    printf("\t1 << (i & 7) : ");
    print2(1 << (num & 7));
    printf("\n");
}
 
int main()
{
    int num;
 
    scanf("%d", &num);
 
    eratosthenes();
 
    for (int i = 1; i <= num; i++) {
        printf("%d --> \t", i);
        printState(i);
 
        if (isPrime(i))    printf("yes\n");
        else               printf("no\n");
    }
    
    return 0;
}

#include <stdio.h>
#include <string.h>
 
#define MAX_N        1000
 
typedef unsigned char    type;
 
type prime[(MAX_N + 7) / (sizeof(type) * 8)];
int bitsize = sizeof(type) * 8;
int bitinit;
 
int bitSize(int num) {
    int n = 0;
    while ((1 << n) <= num)    n++;
    return n - 1;
}
 
void init()
{
    bitinit = bitSize(bitsize);
}
 
type isPrime(int num) {
    return prime[num >> bitinit] & (1 << (num & (bitsize - 1)));
}
 
void setComposite(int num) {
    prime[num >> bitinit] &= ~(1 << (num & (bitsize - 1)));
}
 
void eratosthenes() {
    int i, j;
 
    memset(prime, ((1 << bitsize) - 1), sizeof(prime));
 
    setComposite(0);
    setComposite(1);
 
    for (i = 2; i * i <= MAX_N; i++) {
        if (isPrime(i)) {
            for (j = i * i; j <= MAX_N; j += i) {
                setComposite(j);
            }
        }
    }
}
 
int main()
{
    int n, i;
    int num;
 
    eratosthenes();
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++) {
        scanf("%d", &num);
        if (isPrime(num))    printf("yes\n");
        else                 printf("no\n");
    }
 
    return 0;
}