C++ में बिटवाइज सीव (Bitwise Sieve)

इस समस्या में, हमें एक संख्या N दी गई है। हमारा कार्य बिटवाइज सीव (Bitwise Sieve) का उपयोग करके N से छोटी सभी अभाज्य संख्याओं को ढूंढना है।

बिटवाइज सीव, एराटोस्थनीज की छलनी (Sieve of Eratosthenes) का एक अनुकूलित संस्करण है जिसका उपयोग दी गई संख्या से छोटी सभी अभाज्य संख्याओं को ढूंढने के लिए किया जाता है।

उदाहरण

इनपुट - N = 25

आउटपुट - 2 3 5 7 11 13 17 19 23

बिटवाइज सीव सामान्य सीव के समान तरीके से काम करता है। सिर्फ इतना है कि हम बूलियन प्रकार के बजाय पूर्णांकों के बिट्स का उपयोग अभाज्य संख्याओं को दर्शाने के लिए करेंगे। यह स्पेस जटिलता को 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("%d से कम सभी अभाज्य संख्याएं हैं 2\t", N);
    bitWiseSieve(N);
    return 0;
}

आउटपुट

37 से कम सभी अभाज्य संख्याएं हैं 2 3 5 7 11 13 17 19 23 29 31 37