Sieve of Eratosthenes


সীভের এই অ্যালগোরিদমটি প্রাইম সংখ্যার তালিকা বের করার জন্য ব্যবহার করা হয় ।
মোটামুটিভাবে ১০ লক্ষ বা ১ কোটির জন্য এটি বেশ ভাল কাজ করে ।
কিন্তু এর চেয়ে বেশি হলে সেটা টাইম লিমিট ক্রস করতে পারে ।

Complexity: O (n logn * loglogn)

ধাপ :
১. প্রথমে ২ থেকে শুরু করে N পর্যন্ত সংখ্যাগুলোর একটি তালিকা করতে হবে ।
২. এই তালিকা থেকে যেগুলো ২ এর গুনিতক সেগুলো বাদ দিতে হবে ।
৩. বাকী সংখ্যা গুলো থেকে যেগুলো ৩ এর গুনিতক সেগুলো বাদ দিতে হবে ।
৪. এইভাবে square root (N) পর্যন্ত সংখ্যাগুলোর গুনিতক বাদ দিতে হবে।
৫. তালিকায় অবশিষ্ট সংখ্যাগুলোর সবগুলোই প্রাইম !!

উদাহরন :

ধরি, N = 30
list: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30.
Square root of N = 6

তাহলে ২ থেকে ৬ পর্যন্ত সংখ্যা গুলোর গুনিতক এই তালিকা থেকে বাদ দিতে হবে।
প্রথমে ২ এর গুনিতকগুলো বাদ দিলে তালিকাটি হবে এরকম :

list: 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29.

এবার ৩ এর গুনিতকগুলো বাদ দিলে হবে :

list: 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29.

এবার ৪ এর গুনিতক বাদ দিতে হবে । কিন্তু ২ এর গুনিতক বাদ দেয়ার সময় ৪ এর গুনিতকগুলো বাদ হয়ে গেছে। তাই আলাদা করে ৪ এর গুনিতক বাদ দেয়ার কিছু নেই।

এবার ৫ এর গুনিকত বাদ দিতে হবে :

list: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

এবার ৬ এর গুনিতক । একইভাবে, ২ এর গুনিতক বাদ দেয়া মানে ৬ এর গুনিকত বাদ হয়ে যাওয়া ।

অর্থ্যাৎ এবার তালিকায় যতগুলো সংখ্যা আছে তার সবগুলোই প্রাইম

আরো জানার জন্য, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

void sieve ()
{
    int N = 1000000;

    bool mark [N];
    memset (mark, true, N + 2);

    mark [0] = mark [1] = false;

    for ( int i = 4; i < N + 2; i += 2 )
        mark [i] = false;

    for ( int i = 3; i * i <= N + 2; i += 2 ) {
        if ( mark [i] == true ) {
            for ( int j = i * i; j < N + 2; j += 2 * i )
                mark [j] = false;
        }
    }
}

লাইন ৫ : ১০ লক্ষ এলিমেন্টের একটি বুলিয়ান অ্যারে ।
এটিই আমাদের লিস্ট / তালিকা

লাইন ৬ : সবগুলো এলিমেন্ট ট্রু দিয়ে ইনিশিয়ালাইজ করা হল

লাইন ৮ : ০ এবং ১ প্রাইম নয়। তাই এগুলো ফলস করে দিলাম

লাইন ১০ – ১১ : ২ বাদে সকল জোড় সংখ্যা ফলস করে দিলাম
মানে, ২ এর সকল গুনিতক বাদ দিয়ে দিলাম
জোড় সংখ্যাগুলোর মধ্যে একমাত্র প্রাইম হলো ২

লাইন ১৩ : ৩ থেকে শুরু করে Square root of (N)পর্যন্ত লুপ চলবে
কারন এই সংখ্যাগুলোর গুনিতক তালিকা থেকে বাদ দিব
যেহেতু সকল জোড় সংখ্যা আমরা আগেই বাদ দিয়েছি তাই ‘i’এর মান ২ করে বাড়ছে

লাইন ১৪ : যদি mark [i] == true হয় তার মানে হল ‘i’এখনও কাটা হয়নি
তার মানে, ‘i’একটি প্রাইম এবং ‘i’ এর সকল গুনিতক বাদ দিতে হবে

লাইন ১৫ : প্রথমে নিচের লাইনটি লক্ষ্য করি,

for ( int j = 2 * i; j < N + 2; j += i )
mark [j] = false;

'i' এর দ্বিগুন থেকে শুরু করে একেবারে N পর্যন্ত সকল 'i' এর গুনিতক বাদ যাচ্ছে
কাজ দ্রুততর করার জন্য আমরা 'i' * 'i' থেকে শুরু করেছি
কারন এরচেয়ে ছোট 'i''র গুনিতকগুলো আগেই বাদ পড়েছে

যেমন ধরি, 'i' = ৩
তাহলে, ৩ * ২ = ৬ আগেই বাদ পড়েছে, কারন ২ এর একটি গুনিতক ৬

আবার 'i' = ৫ হলে,
৫ * ২ = ১০ আগেই বাদ পড়েছে, কারন ২ এর একটি গুনিতক ১০
৫ * ৩ = ১৫ আগেই বাদ পড়েছে, কারন ৩ এর একটি গুনিতক ১৫ এবং
'i''র মান ৫ হবার আগেই ৩ হয়েছিল এবং তখন ১৫ বাদ পড়েছে

আরেকটি বিষয় হল, এই লুপটিতে 'i' কিন্তু সর্বদা একটি বিড়োজ সংখ্যা
'i' * 'i' = একটি বিজোড় সংখ্যা হবে
তাই আমরা j += iনা করে j += 2 * i করেছি
কারন, একটি বিজোড় সংখ্যার সাথে আর একটি বিজোড় সংখ্যা যোগ করলে
সেগুলো একটি জোড় সংখ্যা উৎপন্ন করে।
'i' * 'i' = বিজোড়, এর সাথে 'i' যোগ করলে একটি জোড় উৎপন্ন হবে।
আর জোড় সংখ্যা গুলো আমরা আগেই বাদ দিয়েছি।

এবার mark [i] == true হলে i একটি প্রাইম
আর, mark [i] == false হলে i প্রাইম নয়।

4 thoughts on “Sieve of Eratosthenes

  1. ওহ জানতাম না চরম হইছে! ধন্যবাদ
    আসলে সময় নিয়ে বসে লেখা হয় না
    চেষ্টা করব আরও লেখার …

  2. আমাকে আগে কেন এই ধরনের সাইটের কথা কেউ বলে নাই।আমি এখন থার্ড ইয়ার এ।এখন কি সম্ভব ভাল প্রগ্রামার হওয়া, কনটেশট এ যাওয়া?pls suggest me,what should i do?

  3. @Jahangir Alam
    আগে কেন কেউ বলে নাই, সেটা তো আমি বলতে পারি না। :p
    একজন ভাল প্রোগ্রামার হতে অনেক অনেক শ্রম দিতে হয়, সময় দিতে হয়।
    থার্ড ইয়ারের স্টুডেন্ট ভাল প্রোগ্রামার হতে পারবে না, এমন কথা তো শুনি নাই!
    ফোর্থ ইয়ারের স্টুডেন্ট, এমনকি ইয়ার মিস করেও অনেকেই কনটেস্ট করে। আমারও তাই ইচ্ছা
    গতকাল কিছু একটা করতে পারি নাই বলে, আজ সেটা করা নিষিদ্ধ হয়ে যায় না। সবকিছুর মূলেই রয়েছে ইচ্ছাশক্তি।
    আমার শুভপ্রত্যাশা রইল …. 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s