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

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

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

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

- Algorithm -

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

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

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

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

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

// K가 소수인지 확인한다.

inline bool isPrime(int k)

{

    return sieve[k >> 3] & (1 << (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] & (1 << (k & 7));

}

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

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

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

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

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

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

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

소스 코드 : 

#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] & (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(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] & (1 << 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 % 8 == 0)
            printf("\n");
    }
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>