প্রাইম নাম্বার - সিভ অফ এরাটস্থেনিজ (Prime Number - Sieve of Eratosthenes)

Aug 4, 2013

আগের পর্বঃ প্রাইম নাম্বার - বেসিক

প্রাইম নাম্বারের বেসিক কনসেপ্টগুলো নিয়ে আগের পর্বে আলোচনা করা হয়েছে। এই পর্বে আমরা কিভাবে 1 থেকে শুরু করে n পর্যন্ত সকল প্রাইম নাম্বার বের করতে পারি তার একটা এফিসিয়েন্ট এলগোরিদম নিয়ে আলোচনা করব। এই এলগোরিদমটির নাম হল ‘সিভ অফ এরাটস্থেনিজ’।

সিভ মানে হল ছাঁকনি। এই এলগোরিদমে কম্পোজিট নাম্বারগুলো থেকে প্রাইম নাম্বারগুলোকে ছেঁকে আলাদা করা হয়। আর গ্রিক গণিতবিদ এরাটস্থেনিজ (২৭৬ পূর্বাব্দ - ১৯৫ পূর্বাব্দ) এই এলগোরিদমের আবিষ্কারক বিধায় এলগোরিদমটির নাম দেওয়া হয়েছে ‘সিভ অফ এরাটস্থেনিজ’। দ্রুততার সাথে প্রাইম নাম্বার বের করার ক্ষেত্রে এলগোরিদমটি এতোটাই কার্যকর যে ২২০০ বছরের পুরোনো এই এলগোরিদম আজও কম্পিউটার বিজ্ঞানে ব্যবহার করা হয়! এর সাহায্যে ১০ মিলিয়নের মধ্যে অবস্থিত সকল প্রাইম নাম্বার অনায়াসেই বের করে ফেলা যায়।

প্রত্যেকটি কম্পোজিট নাম্বারকেই কতগুলো প্রাইম নাম্বারের গুণিতক হিসেবে প্রকাশ করা যায়। এটি নাম্বার থিওরির একটা বেসিক থিওরি। অর্থাৎ n যদি একটি কম্পোজিট নাম্বার হয় তাহলে,

n = p1 x p2 x p3 x … x pk ; এখানে p1, p2, p3, … , pk সকলেই প্রাইম নাম্বার

এখন এই প্রাইম ফ্যাক্টরগুলোর মধ্যে অন্তত একটি প্রাইম ফ্যাক্টর থাকবেই যেটি √n এর সমান বা ছোট হবে। অন্যভাবে বলা যায় যদি একটি প্রাইম ফ্যাক্টর √n এর থেকে বড় হয় তাহলে বাকিগুলোর থেকে অন্তত একটিকে অবশ্যই √n এর থেকে ছোট হতেই হবে। যদি তা না হয়, অর্থাৎ যদি দুটি প্রাইম ফ্যাক্টর √n এর থেকে বড় হয় তাহলে তাদের গুণফল n এর থেকে বড় হয়ে যাবে যেটি সম্ভব নয়। অতএব একটি নাম্বার যদি প্রাইম না হয়, অর্থাৎ কম্পোজিট নাম্বার হয় তাহলে তার বর্গমূলের সমান অথবা ছোট অন্তত একটি প্রাইম নাম্বার থাকবেই যাকে দিয়ে ঐ নাম্বারটিকে ভাগ করা যাবে। এই কনসেপ্টটাই ব্যবহার করা হয় সিভ অফ এরাটস্থেনিজে।

ধরা যাক আমাদেরকে 1 থেকে 120 পর্যন্ত সকল প্রাইম নাম্বার বের করতে হবে। সংজ্ঞানুযায়ী 1 প্রাইম নাম্বার না। তাই শুরুতেই এটিকে আমরা বাদ দিয়ে দিলাম। এখন আমরা ধরে নিব যে যতগুলো নাম্বার আছে, অর্থাৎ 2 থেকে 120 পর্যন্ত তাদের সবগুলোই প্রাইম। এবার আমরা ছোট থেকে শুরু করে একটা করে প্রাইম নাম্বার নিব এবং সেটিকে রেখে তার গুণিতক গুলোকে কেটে দিব কারণ সেগুলো কম্পোজিট। এরপর এর পরের প্রাইম নাম্বার অর্থাৎ যেটি কেটে ফেলা হয়নি সেটি নিয়ে তার সবগুলো গুণিতককে আমরা কেটে দিব। এরপর তার পরবর্তি প্রাইম নাম্বার নিব এবং এভাবে বার বার একই কাজ করতে থাকব।

এখন কথা হল কতক্ষণ আমরা এটা করব? আগেই বলা হয়েছে কম্পোজিট নাম্বারের বর্গমূলের সমান বা ছোট একটি প্রাইম ফ্যাক্টর থাকবেই। এখানে আমাদের সর্বোচ্চ নাম্বার হল 120। এটি যদি কম্পোজিট হয় তাহলে এর বর্গমূল √120 এর মধ্যে অবস্থিত যেকোন একটি প্রাইমের গুণিতক হিসেবে এটি কেটে বাদ পড়ে যাবে। ফলে আমরা √120 পর্যন্ত প্রাইম নাম্বারগুলো দিয়ে এই কাজ করতে থাকব। আর 120 এর থেকে ছোট সকল নাম্বারের বর্গমূলও √120 অপেক্ষা ছোট হবে। তাই √120 পর্যন্ত প্রাইম নাম্বার নিয়ে কাটতে থাকলে ওগুলো কম্পোজিট হলে এর মধ্যে এমনিতেই বাদ পরে যাবে।

এই কাজটিই এখন এনিমেশনের মাধ্যমে দেখা যাক। (উৎসঃ উইকিপিডিয়া)

এই কাজটিকে এখন যদি আমরা কোডে লিখতে চাই তাহলে কিভাবে করব? যেহেতু আমরা একটা লিস্ট থেকে কিছু নাম্বার রাখছি আর কিছু নাম্বার বাদ দিচ্ছি, তাই আমরা পুরো কাজটির জন্য একটা অ্যারে নিব। সেই অ্যারের ইন্ডেক্স আমাদের নাম্বার নির্দেশ করবে, আর অ্যারেতে আমরা সত্য অথবা মিথ্যা রাখব। একটি দিয়ে আমরা বোঝাবো যে ইন্ডেক্সের নাম্বারটি প্রাইম, অন্যটি দিয়ে বোঝাবো প্রাইম না। যেহেতু আমরা অ্যারের এলিমেন্টে কেবল দুটি ভেলু রাখবো তাই শুধু শুধু ৩২ বিটের ইন্টিজার অ্যারে নিয়ে মেমরি নষ্ট করার কোন মানে নেই। আমরা bool বা char অ্যারে দিয়েই কাজটি করতে পারি। bool নিলে আমরা true/false রাখবো, আর char নিলে 1 বা 0 রাখবো। নিচে কোডটি দেখানো হল -

#define MAX 1000001
char prime[MAX]; // 0 দিয়ে initialize করতে হবে
// prime[index] এ যদি 0 থাকে তাহলে index একটি প্রাইম নাম্বার
// আর যদি 1 থাকে তাহলে index প্রাইম না
void primeGenerator( int n ) // n পর্যন্ত প্রাইম বের করব
{
    int x = sqrt( n );
    prime[0] = prime[1] = 1;       // 0 এবং 1 প্রাইম না
    for( int i = 2; i <= x; i++ ) {
        if( prime[i] == 0 ) {      // i যদি মৌলিক সংখ্যা হয় তাহলে 2i
            for( int j = i+i; j <= n; j += i ) // থেকে শুরু করে i
                prime[j] = 1;      // এর সকল গুণিতককে বাদ দিয়ে দিব
        }
    }
    return;
}

আশা করি কোডটি বুঝতে কারও সমস্যা হবে না। উপরের কথাগুলোকেই কোডে রূপান্তর করা হয়েছে। না বুঝলে উপরের লেখাগুলো আবার পড়তে অনুরোধ করব। সংক্ষেপে বললে, আমরা 2 থেকে √n পর্যন্ত লুপ চালাচ্ছি। যদি নাম্বারটি প্রাইম হয় তাহলে আরেকটি লুপ চালিয়ে তার গুণিতকগুলোকে কম্পোজিট হিসেবে নির্দেশ করছি। এই কোডটিকে আরেকটু এফিসিয়েন্ট করা যায়। আমরা i এর মান ১ করে না বাড়িয়ে শুরুতেই সবগুলো জোড় সংখ্যাকে বাদ দিয়ে দিতে পারি। তারপর i এর মান 3 থেকে শুরু করে 2 করে বাড়াতে পারি। কারণ এটি খুবই সহজবোধ্য একটা ব্যাপার যে কোন 2 ব্যতীত কোন জোড় সংখ্যা প্রাইম হতে পারবে না। তাই শুধু শুধু সেগুলোতে লুপ চালানোর কোন দরকার নেই।

#define MAX 1000001
char prime[MAX]; // 0 দিয়ে initialize করতে হবে
void primeGenerator( int n ) // n পর্যন্ত প্রাইম বের করব
{
    int x = sqrt( n );
    prime[0] = prime[1] = 1;         // 0 এবং 1 প্রাইম না
    for( int i = 4; i <= n; i += 2 ) // জোড় সংখ্যাগুলোকে বাদ দিয়ে দিব
        prime[i] = 1;
    for( int i = 3; i <= x; i += 2 ) {
        if( prime[i] == 0 ) {      // i যদি মৌলিক সংখ্যা হয় তাহলে 2i
            for( int j = i+i; j <= n; j += i ) // থেকে শুরু করে i
                prime[j] = 1;      // এর সকল গুণিতককে বাদ দিয়ে দিব
        }
    }
    return;
}

এখানে ভিতরের লুপটাতে j = i + i এর পরিবর্তে j = i x i লেখা যায়। অর্থাৎ আমরা চাইলে লুপটিকে আরেকটু বড় নাম্বার থেকে শুরু করে চালাতে পারি। i এর মান যখন অনেক ছোট তখন এটি তেমন কোন প্রভাব না ফেললেও বড় নাম্বারের জন্য রানটাইম একটু কমানো সম্ভব। তবে কেন i x i লিখলেও হবে সেটি নিজে থেকে চিন্তা করার দায়িত্ব থাকল।

এভাবে সিভ অফ এরাটস্থেনিজের মাধ্যমে আমরা খুব সহজেই এবং অনেক দ্রুত গতিতে অনেক বড় নাম্বার পর্যন্ত সীমার মধ্যে সবগুল প্রাইম বের করে ফেলতে পারি। এই এলগোরিদমের টাইম কমপ্লেক্সিটি O( n ( log n ) ( log log n ) ) যা আমাদের গত পর্বের এলগোরিদমের কম্পেক্সিটি O(n^2) অপেক্ষা অনেক ভালো। এছাড়াও আরো এফিসিয়েন্ট এলগোরিদম রয়েছে যেগুলো নিয়ে পরবর্তিতে আলোচনা করা হবে।

আমরা এখানে char টাইপের অ্যারে নিয়েছি। কিন্ত দেখাই যাচ্ছে আমরা একটা নাম্বারের জন্য কেবল 1 বা 0 রাখছি যা একটি বিট দিয়েই হয়ে যায়। শুধু শুধু ৮ বিটের মেমরির বাকি ৭ বিট নষ্ট হচ্ছে। 1000000 টি এলিমেন্টের জন্য 7000000 বিট নষ্ট হচ্ছে। এতোখানি মেমরি নষ্ট না করে আমরা বিট-ওয়াইজ সিভ ব্যবহার করে একটা নাম্বারকে একটা বিটের সাহায্যে প্রাইম নাকি কম্পোজিট তা নির্দেশ করতে পারি।

প্র্যাকটিস প্রবলেমঃ
১। UVa 543 - Goldbach’s Conjecture
২। UVa 686 - Goldbach’s Conjecture (II)
৩। UVa 10394 - Twin Primes
৪। UVa 10533 - Digit Primes

পরবর্তি পর্বঃ প্রাইম নাম্বার – বিট-ওয়াইজ সিভ