এই সমস্যায়, আমাদের একটি সংখ্যা দেওয়া হয়েছে। আমাদের কাজ হল বিটওয়াইজ সিভ ব্যবহার করে N থেকে ছোট সব মৌলিক সংখ্যা খুঁজে বের করা।
Bitwise চালনী হল 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("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
