Bitwise Sieve ใน C++

ในปัญหานี้ เราได้รับตัวเลข N ภารกิจคือการหาจำนวนเฉพาะทั้งหมดที่น้อยกว่า N โดยใช้ Bitwise Sieve

Bitwise sieve เป็นเวอร์ชันที่ปรับปรุงประสิทธิภาพของ Sieve of Eratosthenes ซึ่งใช้หาจำนวนเฉพาะทั้งหมดที่น้อยกว่าตัวเลขที่กำหนด

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต − N = 25

เอาต์พุต − 2 3 5 7 11 13 17 19 23

Bitwise sieve ทำงานเหมือน Sieve ธรรมดา แต่มันใช้บิตของจำนวนเต็มเพื่อแทนจำนวนเฉพาะแทนที่จะใช้ boolean type ทำให้ลดความซับซ้อนด้านพื้นที่ (space complexity) ลงเหลือ 1/8 เท่า

ตัวอย่างโปรแกรม

#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