इस समस्या में, हमें एक नंबर N दिया जाता है। हमारा काम बिटवाइज़ चलनी का उपयोग करके N से छोटी सभी अभाज्य संख्याओं को खोजना है।
बिटवाइज़ चलनी, सीव ऑफ़ एराटोस्थनीज़ का एक अनुकूलित संस्करण है जिसका उपयोग दी गई संख्या से छोटी सभी अभाज्य संख्याओं को खोजने के लिए किया जाता है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट -एन =25
आउटपुट - 2 3 5 7 11 13 17 19 23
बिटवाइज़ चलनी सामान्य चलनी की तरह ही काम करती है। यह सिर्फ हम एक बूलियन प्रकार के बजाय प्रतिनिधित्व primes के पूर्णांक के बिट्स का उपयोग करेंगे। यह अंतरिक्ष की जटिलता को 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