Sàng bitwise trong C++

Sàng bitwise hoạt động giống sàng thường, chỉ khác là dùng các bit của số nguyên để biểu diễn số nguyên tố thay vì mảng boolean. Điều này giảm độ phức tạp không gian xuống 1/8.

Ví dụ

Code minh họa:

#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*i <= n; i += 2) {
        if (!ifnotPrime(prime, i))
            for (int j=i*i, 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;
}

Đầu ra

All the prime number less than 37 are 2 3 5 7 11 13 17 19 23 29 31 37