এই সমস্যাতে, আমাদের একটি সংখ্যা N দেওয়া আছে। আমাদের কাজ হলো বিটওয়াইজ সিব ব্যবহার করে N-র চেয়ে ছোট সব প্রাইম নম্বর বের করা।
বিটওয়াইজ সিব হলো এরাটোস্থেনিসের সিবের একটি অপ্টিমাইজড ভার্সন যা দেওয়া সংখ্যা থেকে ছোট সব প্রাইম নম্বর বের করতে ব্যবহৃত হয়।
উদাহরণ দিয়ে বুঝি,
ইনপুট − N = 25
আউটপুট − 2 3 5 7 11 13 17 19 23
বিটওয়াইজ সিব সাধারণ সিবের মতোই কাজ করে। পার্থক্য শুধু এটাতে আমরা প্রাইম রিপ্রেজেন্ট করতে বুলিয়ান টাইপের বদলে ইন্টিজারের বিট ব্যবহার করি। এটি স্পেস কমপ্লেক্সিটি ১/৮ গুন করে দেয়।
উদাহরণ
কোডটি দেখে সমাধান বুঝুন,
#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
