ইরাটোস থেনিসের সিভ(Sieve of Eratosthenes)

একটি নাম্বার প্রাইম কিনা তা আগের পর্বে দেখেছি sqrt(n) সময়ে। যদি বলা হয় 1 থেকে 1000000 পর্যন্ত প্রাইম নাম্বার গুলো বের করতে, সময় 1 সেকেন্ড।

এখন কিন্তু আগের মত করে বের করতে গেলে 1 সেকেন্ডে বের করা সম্ভব না। বর্তমানের কম্পিউটারগুলো 1 সেকেন্ডে প্রায় 100000000 টি কাজ করতে পারে কিন্তু এখানে কমপ্লেক্সিটি হয়ে যাচ্ছে O(1000000 * sqrt(1000000)) প্রায়, মানে 1000000000। অবাক করার মত বিষয় হচ্ছে এই সমস্যা অনেক আগেই ইরাটোস থেনিস নামের এক গণিতজ্ঞ সমাধান করে গেছেন একটি অ্যালগরিদম বের করে। যিনি জন্মেছিলেন খ্রিস্টপূর্ব ২৭৬ সালে!!! সেই অ্যালগরিদম কে ইরাটোস থেনিসের ছাঁকনি বা সিভ(Sieve) বলা হয়। 

অ্যালগরিদম টি খুব সহজ, 1 থেকে n পর্যন্ত প্রাইম নাম্বার গুলো বের করতে চাইলে 1 থেকে n পর্যন্ত নাম্বার গুলো আমি আগে খাতায় লিখে নিব। এখন, প্রথম প্রাইম 2 এর গুণিতক বা মাল্টিপল গুলো কেটে দিব। এরপর দ্বিতীয় প্রাইম 3 এর মাল্টিপল গুলো কেটে দিব। এভাবে শেষ করার পর যে নাম্বার গুলো কাটা পরেনি তারা সবাই প্রাইম। 

কার্টেসি(GIF Source): উইকিপিডিয়া

এখন, কিছু প্রশ্ন আসতে পারে তা হচ্ছে, প্রাইম এর মাল্টিপল গুলো কেটে দিব কিন্তু একটি নাম্বার প্রাইম কিনা সেটি বুঝব কীভাবে? আবার, কখন ই বা প্রাইম এর মাল্টিপল গুলো কাটা বন্ধ করে দিব? আমরা জানি, প্রথম প্রাইম হচ্ছে 2। তাই শুরু করব 2 থেকে। অ্যালগরিদমের শেষে বলা আছে, যে নাম্বার গুলো কাটা যাবে না তারাই প্রাইম। তাহলে, 2 থেকে n পর্যন্ত এক এক করে যাবো এবং বর্তমানে আমি যে নাম্বারে আছি তা যদি ইতিমধ্যে কাটা না পরে থাকে তাহলে সেটি প্রাইম এবং তার মাল্টিপল গুলো কেটে দিব যারা n থেকে ছোট অথবা সমান। আর কিছু ভিন্ন n এর জন্য খাতায় লিখে বের করার চেষ্টা করলে দেখা যাবে আসলে 2 থেকে sqrt(n) পর্যন্ত প্রাইম নাম্বারের মাল্টিপল গুলো কেটে দিলেই হয়ে যাচ্ছে।

const int N = 1e6; vector <int> prime; bool mark[N+1]; void sieve() {   /// 0 and 1 is marked as not prime   mark[0] = true;   mark[1] = true;   int lim = sqrt(N);   for (int i = 2;i <= lim;i++) {     if (mark[i] == false){       /// if mark[i] is false then i is prime       for (int j = i+i;j <= N;j += i) {         /// multiple of i marked as not prime         mark[j] = true;       }     }   }   for (int i = 2;i <= N;i++) {     if (mark[i] == false) {       prime.push_back(i);     }   } }

একটি বিষয় লক্ষণীয়, যেহেতু 2 ছাড়া বাকি সব প্রাইমই বিজোড় তাই 2 এর মাল্টিপল গুলো কেটে দেওয়ার পরে 3 থেকে শুরু করে দুই ঘর পর পর যেতে পারি। তাহলে, শুধু বিজোড় নাম্বারগুলো দেখা হবে আর কাজ ও কিছু কমে যাচ্ছে।

const int N = 1e6; vector <int> prime; bool mark[N+1]; void sieve() {   /// 0 and 1 is marked as not prime   mark[0] = true;   mark[1] = true;   /// multiple of 2 marked as not prime   for (int i = 4;i <= N;i += 2) {     mark[i] = true;   }   int lim = sqrt(N);   for (int i = 3;i <= lim;i += 2) {     if (mark[i] == false){       /// if mark[i] is false then i is prime       for (int j = i+i;j <= N;j += i) {         /// multiple of i marked as not prime         mark[j] = true;       }     }   }   for (int i = 2;i <= N;i++) {     if (mark[i] == false) {       prime.push_back(i);     }   } }

এটিরো আরো কিছু অপটিমাইজেশন সম্ভব। যেমন, প্রতিটা মাল্টিপল না চেক করলেও চলে। প্রাইমের বর্গ থেকে শুরু করে প্রাইম + প্রাইম ঘর পর পর কেটে দিলেই হয়ে যাবে। এতে অ্যালগরিদম টি আরো দ্রুত হবে।

আচ্ছা তাহলে এটির কমপ্লেক্সিটি কত? মেমোরি কমপ্লেক্সিটি হবে O(prime.size()+(N/4)) যদি আমরা চার বাইট কে এক ইউনিট করে ধরি। আর যেহেতু bool টাইপ এক বাইট করে জায়গা দখল করে। যদি প্রাইম নাম্বার গুলো রাখার জন্য অতিরিক্ত অ্যারে ব্যবহার না করতাম তাহলে এর মেমোরি কমপ্লেক্সিটি হত O(N)। 

টাইম কমপ্লেক্সিটি O(N * log(N)) এর কম।

এই বিষয়ে আরো টিউটোরিয়াল।
টিউটোরিয়াল ১

প্র্যাক্টিস প্রবলেমঃ

N-th Prime