문제 개요
하나의 숫자 N이 주어졌을 때, 비트와이즈 체(Bitwise Sieve)를 활용해 N보다 작은 모든 소수를 찾는 것이 이번 글의 목표입니다.
비트와이즈 체는 널리 알려진 에라토스테네스의 체(Sieve of Eratosthenes)를 최적화한 알고리즘으로, 주어진 수보다 작은 모든 소수를 빠르고 효율적으로 구할 수 있습니다.
문제 예시
입력: N = 25
출력: 2 3 5 7 11 13 17 19 23
비트와이즈 체의 동작 원리
비트와이즈 체는 일반적인 에라토스테네스의 체와 동일한 방식으로 동작합니다. 결정적인 차이점은 불리언(boolean) 배열 대신 정수형 변수의 각 비트(bit)를 사용해 소수 여부를 표현한다는 점입니다.
int형 하나는 32비트이므로, 기존 방식에서 값 하나당 1바이트씩 차지하던 공간을 비트 단위로 압축할 수 있습니다. 그 결과 공간 복잡도가 기존의 1/8 수준으로 줄어들어, 매우 큰 범위의 소수를 구할 때도 메모리를 크게 절약할 수 있습니다.
여기에 더해, 2를 제외한 모든 짝수는 소수가 아니므로 홀수만 검사 대상으로 삼는 최적화도 함께 적용됩니다.
C++ 구현 코드
#include <iostream>
#include <math.h>
#include <cstring>
using namespace std;
bool ifnotPrime(int prime[], int x) {
return (prime[x/64] & (1 << ((x >> 1) & 31)));
}
bool makeComposite(int prime[], int x) {
prime[x/64] |= (1 << ((x >> 1) & 31));
}
void bitWiseSieve(int n) {
int prime[n/64];
memset(prime, 0, sizeof(prime));
for (int i = 3; i <= sqrt(n); i = i + 2) {
if (!ifnotPrime(prime, i))
for (int j = pow(i, 2), k = i << 1; j < n; j += k)
makeComposite(prime, j);
}
for (int i = 3; i <= n; i += 2)
if (!ifnotPrime(prime, i))
printf("%d\t", i);
}
int main() {
int N = 37;
printf("All the prime number less than %d are 2\t", N);
bitWiseSieve(N);
return 0;
}
실행 결과
All the prime number less than 37 are 2 3 5 7 11 13 17 19 23 29 31 37
코드 상세 설명
핵심 함수들의 역할은 다음과 같습니다.
- ifnotPrime() – x에 해당하는 비트가 이미 설정되어 있는지 확인합니다. 설정되어 있다면 그 수는 합성수(composite)라는 뜻입니다.
- makeComposite() – i²부터 시작해 i의 홀수 배수에 해당하는 비트를 1로 설정해 합성수로 표시합니다.
- bitWiseSieve() – 3부터 √n까지의 홀수에 대해 위 과정을 반복해 체를 수행한 뒤, 남아 있는 소수를 출력합니다.
x/64 인덱싱과 (x >> 1) & 31 오프셋 계산은 하나의 int(32비트) 안에 짝수를 제외한 64개의 수 정보를 담기 위한 비트 조작 기법입니다. 내부 루프에서 k = i<<1, 즉 2i씩 건너뛰는 이유는 짝수 배수를 건너뛰기 위함입니다.
참고로 위 코드는 마지막 루프 조건이 i <= n이므로 N 자체도 함께 출력됩니다. N 미만의 소수만 필요하다면 조건을 i < n으로 바꾸면 됩니다.
마무리
비트와이즈 체는 시간 복잡도가 에라토스테네스의 체와 동일한 O(N log log N) 수준이면서도 메모리 사용량을 1/8로 줄여주기 때문에, 큰 범위의 소수를 구해야 하는 문제에서 특히 유용한 알고리즘입니다.