:: ADVANCE ::

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

Algorithm/Algorithm

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

KSJ14 2016. 7. 17. 01:16
반응형

[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로 줄일 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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, 255sizeof(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;
}
cs




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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;
}
cs


반응형

'Algorithm > Algorithm' 카테고리의 다른 글

[MST] 크루스칼 알고리즘  (0) 2016.10.14
[Bit] bit 개수 세는 함수  (0) 2016.10.12
[STL] vector  (0) 2016.07.04
[STL] 어댑터  (0) 2016.07.02
[STL] 알고리즘  (0) 2016.07.02
Comments