반응형

비트 마스크를 이용하지 않은 에라토스테네스의 체는 

http://programbasic.tistory.com/576에서 확인 할 수 있다.


알고리즘을 보면 다음과 같다.


- Algorithm -


1. 2부터 N까지 모든 수를 쓴다.


2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.


3. 그 수를 지우고 소수로 저장한다.


4. 이제 그 수의 배수를 모두 지운다.


이 방식을 그대로 이용하여 비트 마스크를 이용한 에라토스테네스의 체를 이용하면 아래 소스 코드와 같다.


// K가 소수인지 확인한다.
inline bool isPrime(int k)
{
    return sieve[k >> 3& (<< (k & 7));
}


이 부분의 k>>3은 8로 나눈 몫과 같고, k & 7은 8로 나눈 나머지를 의미하는 것과 같다.


    int sqrtn = int(sqrt(n));
    for (int i = 2; i <= sqrtn; ++i)
        // 이 수가 아직 지워지지 않았다면
        if (isPrime(i))
            // i의 배수 j들에 대해 isPrime[i] = false로 둔다.
            // i*i 미만의 배수는 이미 지워졌으므로 신경 쓰지 않는다.
            for (int j = i*i; j <= n; j += i)
                setComposite(j);


이 부분에서 위의 알고리즘이 동작하게 되고


// K가 소수인지 확인한다.
inline bool isPrime(int k)
{
    return sieve[k >> 3& (<< (k & 7));
}


이 부분에서 원하는 k가 소수 인지 확인할 수 있게 된다.


그리고 최종적으로 비트 마스크를 이용한 에라토스테네스의 체의 해를 알고 싶다면


3가지 방식의 출력 형식을 구현할 수 있다.


1. bitset STL을 이용한 방식 :: http://www.crocus.co.kr/549


2. 비트 연산을 이용한 방식


3. isPrime을 이용한 방식이 존재한다.







소스 코드 아래에 출력 화면을 수록해 두었다.


소스 코드 : 


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
82
83
84
85
86
#include <iostream>
#include <cstdio>
#include <bitset>
 
#define MAX_N 100
 
using namespace std;
 
int n;
 
unsigned char sieve[(MAX_N + 7/ 8];
 
// K가 소수인지 확인한다.
inline bool isPrime(int k)
{
    return sieve[k >> 3& (<< (k & 7));
}
 
// k가 소수가 아니라고 표시한다.
inline void setComposite(int k)
{
    sieve[k >> 3&= ~(<< (k & 7));
}
 
// 비트 마스크를 사용하는 에라토스테네스의 체의 구현
// 이 함수를 수행하고 난 뒤, isPrime()을 이용해 각 수가 소수인지 알 수 있다.
void eratosthenes()
{
    memset(sieve, 255sizeof(sieve));
    setComposite(0);
    setComposite(1);
 
    int sqrtn = int(sqrt(n));
    for (int i = 2; i <= sqrtn; ++i)
        // 이 수가 아직 지워지지 않았다면
        if (isPrime(i))
            // i의 배수 j들에 대해 isPrime[i] = false로 둔다.
            // i*i 미만의 배수는 이미 지워졌으므로 신경 쓰지 않는다.
            for (int j = i*i; j <= n; j += i)
                setComposite(j);
}
 
int main()
{
    n = 100;
    eratosthenes();
    bitset<8> bt;
    
    printf("\nbitset으로 나타낸 소수 확인 방식\n");
    for (int i = 0; i < ((MAX_N + 7/ 8); i++)
    {
        bt = sieve[i];
 
        cout << bt << endl;
    }
 
    printf("\n비트 연산으로 나타낸 소수 확인 방식\n");
    for (int i = 0; i < (MAX_N + 7/ 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            if (sieve[i] & (<< j))
                printf("1");
            else
                printf("0");
        }
 
        cout << endl;
    }
 
    printf("\nisPrime을 이용하여 나타낸 소수 확인 방식\n");
    int cnt = 0;
    for (int i = 0; i < MAX_N; i++)
    {
        isPrime(i) ? printf("1") : printf("0");
 
        cnt++;
        if (cnt % == 0)
            printf("\n");
    }
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




여기서 주목할 점은

isPrime외에 2가지에서 나타낸 것은 

7   6   5   4  3   2 1 0

15 14 13 12 11 10 9 8

...

순으로 오른쪽에서 부터 나타나고


isPrime에는 왼쪽에서 부터 0이 소수인지 확인해준다.


그리고 bitset과 비트 연산은 범위가 i < (MAX_N + 7) / 8이기에 

isPrime의 가장 아랫값인 0100이상으로 조금 더 나타남을 볼 수 있다.

       




반응형