Seieve of Eratosthenes

 সিভ অফ এরাটোসথেনিসের ইফিসিয়েন্ট ভার্সনঃ

বিটওয়াইজ সিভ 

প্রথমে কোডটা দেখা যাকঃ 

---

কোডঃ

 

// bitwise Seieve of Eratosthenes
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define ui unsigned int
#define ull unsigned long long int
#define nl puts("")
#define MX 105
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

int prime[1];
// vagfol dibe. oi vagfoler soman index e giye index number er bit ke set korbe 
int setbit(int n, int pos)
{
    n = n | (1<<pos); // 1<<pos mane 2^pos
    return n;
}
// vagshesh dibe. oi vagshesh tomo bit ke check korbe
bool checkbit(int n, int pos)
{
    n = n & (1<<pos);
    return n;
}

void seieve(int n)
{
    int x=sqrt(n),i,j;

    prime[0]=setbit(prime[0],0); // initialize korlam 0 diye
    prime[0]=setbit(prime[0],1); // initialize korlam 1 diye

    for(i=4;i<=n;i+=2)
    {
        prime[i>>5] = setbit( prime[i>>5], i&31);
    }
// i>>5 mane i ke 32 diye vag kore vagfol. i&31 mane i ke 32 diye vag kore vagshesh
    for(i=3;i<=x;i+=2)
    {
        if(!checkbit(prime[i>>5],i&31))
        {
            for(j=i+i;j<=n;j+=i)
            {
                prime[j>>5]=setbit( prime[j>>5] , j&31 );
            }
        }
    }
}

int main()
{
    int n,i; cin >> n; int d=n;

    seieve(n);

    lp2(i,n)
    {
        if(!checkbit( prime[i>>5], i&31 ))
        {
            cout << i ;

            if(d>0) // space control kora hoise just.
            {
                cout << " ";
                d--;
            }
        }
    }

    nl;

    return 0;
} 

---

এই সিভের মাধ্যমে আমরা n পর্যন্ত সব গুলু নাম্বারের প্রাইম জেনারেইট করব । এজন্য আমরা একটি অ্যারে ডিক্লেয়ার করে দিলাম আগে । এই অ্যারের কাজ হচ্ছে সে প্রতিটি ইন্ডেক্সের প্রতিটি ইলিমেন্টের বিট গুলু কে ফ্ল্যাগিন (নির্দেশক) করবে ।
কি বুঝা যাচ্ছে না তো ??
আচ্ছা, আমরা জানি int হল ৩২ বিট মেমরির ডাটা টাইপ । এবং অ্যারের সাইজ হতে হবে [n+1] যা অ্যারের বেসিক কনসেপ্ট । এখন n এর মান যদি 5 হয় । তাহলে 0 থেকে 5 পর্যন্ত অ্যারেটি দেখতে এইরকম হবে ...

---

 
position                            ...8 7654 3210
prime[0] = 0000 0000 0000 0000 0000 0000 0001 0011 

---

তো এই যে প্রতি অ্যারের ১ টি বিট ছাড়া নাকি ৩১ টি বিট অব্যবহৃত থেকে যাচ্ছে তার প্রতিটিকে আমরা  ফ্ল্যাগিন বা নির্দেশক করব ।

আর এতে করে আমরা ১টি অ্যারে ইলিমেন্টের মাধ্যমে ৩২ টি নাম্বার কে প্রকাশ করতে পারব । তার মানে একই সাইজের অ্যারেতে আমরা আগের রেঞ্জের ৩২ গুন পর্যন্ত প্রাইম নাম্বার জেনারেইট করতে পারব । 

আর এতে করে prime[0] এর জন্য 0 থেকে 31 পর্যন্ত নাম্বার গুলুর ফ্ল্যাগ থাকবে । এবং দ্বিতীয় এলিমেন্ট বা prime[1] এ 32 থেকে 63 পর্যন্ত নাম্বারগুলোর ফ্ল্যাগ থাকবে, এভাবে চলতে থাকবে ...

এখন আমরা দেখব যে, setbit এবং checkbit কি কাজ করেঃ

সিভে লুপের মধ্যে যখন কোন নাম্বার আসবে তখন সেই নাম্বারটিকে 32 দিয়ে ভাগ করব ( বলে রাখি বিটওয়াজে ৩২ = ২^৫ লিখতে গেলে 1<< 5 এইভাবে লিখতে হয়। )। ভাগফল যত হবে তত নাম্বার ইন্ডেক্সে নাম্বারটির ফ্ল্যাগ আছে। এখন কোন বিটটি ফ্ল্যাগ হবে সেটির জন্য আমরা নাম্বারটিকে 32 দিয়ে mod করব ( বলে রাখি বিটওয়াজে a mod b করতে গেলে  a & (b-1) এইভাবে লিখতে হয়। ) । ভাগশেষ যেটি হবে সেটিই হল নাম্বারটির ফ্ল্যাগের পজিশন।

যেমনঃ

আমরা যদি 4 এর ফ্ল্যাগ সেট করতে চাই অথবা দেখতে চাই ফ্ল্যাগটি 1 নাকি 0 তাহলে prime অ্যারের 4/32 = 0 ইন্ডেক্সের এলিমেন্টে যাব এবং 4%32 = 4 নাম্বার বিটটি সেট করব বা চেক করব। একইভাবে যদি 32 এর জন্য করি তাহলে 32/32 = 1 ইন্ডেক্সের এলিমেন্টে যাব এবং 32%32 = 0 নাম্বার বিটটি চেক করব। এভাবে করে আমরা যেকোন নাম্বারের জন্য কাজটি করতে পারি।
তো আসলে এই কাজ গুলুই করে setbit এবং checkbit । আরো ক্লিয়ারলি বললে setbit n এর পজিশন তম বিট কে সেট করবে এবং checkbit n এর পজিশন তম বিট কে চেক করবে সেটা কোন ফ্ল্যাগে আছে 0 নাকি 1 ।

তো, এইভাবে বিটওয়াইজ সিভ ব্যবহার করে আমরা আমাদের  প্রোগ্রাম কে আরো ইফিসিয়েন্ট এবং আরো ফাস্ট করে তুলতে পারি ।।