সেগমেন্ট সিভ(Segment Sieve)

আমরা এখন জানি, কীভাবে সিভ অ্যালগরিদম দিয়ে 1 থেকে n পর্যন্ত সবগুলো প্রাইম বের করতে হয়। কিন্তু, n এর মান কত বড় এর জন্য পারব? 1000000000 হলে কী পারব? 1 থেকে 1000000000 পর্যন্ত যদি বলা হয় তাহলে বর্তমানের কম্পিউটার দিয়ে সেটি সম্ভব নয় :| তবে, যদি বলা হয় 1 থেকে n পর্যন্ত নির্দিষ্ট একটি সেগমেন্ট মানে L থেকে R পর্যন্ত সবগুলো  প্রাইম বের করতে হবে এবং R-L কখনো 1000000 এর থেকে বড় হবে না। তাহলে n এর ভ্যালু 10000000000000000 হলেও বের করে ফেলতে পারব!!! এক্ষেত্রে আমাদের সেগমেন্ট সিভ অ্যালগরিদম টি ব্যবহার করতে হবে। সেগমেন্ট সিভ সাধারণ সিভের মতই কিন্তু একটু মডিফাই করতে হয়।

আচ্ছা, সাধারণ সিভ অ্যালগরিদমে আমরা কী করতাম? প্রথম প্রাইম 2 থেকে শুরু করে n এর বর্গমূল পর্যন্ত সব প্রাইম দিয়ে n এর থেকে ছোট বা সমান তাদের সব মাল্টিপল গুলো কেটে দিতাম। কিন্তু, সেগমেন্ট সিভ অ্যালগরিদমে প্রথম প্রাইম 2 থেকে শুরু করে R এর বর্গমূল পর্যন্ত সব প্রাইম দিয়ে L থেকে R পর্যন্ত এদের সবগুলো মাল্টিপল কে কেটে দিব। বাকি যা থাকবে তারাই প্রাইম। কিন্তু এখানে R এর ভ্যালু যেহেতু অনেক বড় তাই আমরা mark অ্যারেতে R টি ভেরিয়েবল নিতে পারব না। আসলে 1 থেকে R টি ভেরিয়েবল আমাদের দরকার ও হচ্ছে না। আমাদের শুধু দরকার (R-L)+1 টি ভেরিয়েবল। mark অ্যারের প্রথম ভেরিয়েবল হচ্ছে L, দ্বিতীয় ভেরিয়েবল L+1, এভাবে R পর্যন্ত। তাহলে id (L <= id <= R) যদি কোন প্রাইমের মাল্টিপল হয় তাহলে mark অ্যারের id-L তম পজিশন কাটা যাবে।

এখন, আমরা ত সাধারণ সিভ অ্যালগরিদমে আগে থেকে n এর বর্গমূল পর্যন্ত সবগুলো প্রাইম বের করে নেওয়ার প্রয়োজন হয় নি। কিন্তু, সেগমেন্ট সিভ অ্যালগরিদমে কি প্রয়োজন হবে? হ্যাঁ, এখানে সাধারণ সিভ অ্যালগরিদম দিয়ে আগে 1 থেকে n এর বর্গমূল পর্যন্ত সবগুলো প্রাইম বের করে নিতে হবে। কারণ, আমরা কিন্তু প্রাইম এর মাল্টিপল যারা L এর থেকে ছোট তাদের কে কেটে দিচ্ছি না। এর ফলে L থেকে ছোট নাম্বার গুলো থেকে প্রাইম ও কম্পোজিট আলাদা হচ্ছে না এবং আমাদের অপ্রয়োজনীয় অনেক কাজ বেশি করতে হবে। তবে আবার প্রতিবার R এর বর্গমূল পর্যন্ত প্রাইম গুলো বের করার ও প্রয়োজন নেই। তাই আমরা শুরুতেই 1 থেকে n এর বর্গমূল পর্যন্ত প্রাইম বের করে রেখে দিয়ে R এর বর্গমূল পর্যন্ত প্রাইম গুলো ব্যবহার করব।

const int N = 1e6; vector <int> p; bool mark[N+5]; void sieve() {   // as n = 1000000000 so, we store square root of n   // into len to find primes up to len and store into p array   int len = sqrt(1000000000);   p.push_back(2);   for (int i = 3;i <= len;i += 2) {     if (mark[i] == false) {       p.push_back(i);       for (int j = i*i;j <= len;j += i+i) {         mark[j] = true;       }     }   } } void seg_sieve(int L, int R) {   int len = (R-L)+1; /// length of the segment   for (int i = 0;i < len;i++) {     mark[i] = false;   }   // p[i]*p[i] make sure that p[i] is less then or equal to square root of R   for (int i = 0;i < p.size() && p[i]*p[i] <= R;i++) {     int j = (L+p[i]-1)/p[i] * p[i]; // j will L <= J     if (j==p[i])j += p[i]; /// if j is remain prime     for ( ;j <= R;j += p[i]) {       mark[j-L] = true;     }   }   for (int i = 0;i < len;i++) {     // if mark[i] is false then, L+i is prime     if (mark[i]==false && i+L > 1){       cout << i+L << '\n';     }   } }

প্রোগ্রামে শুরুতে সাধারণ সিভ অ্যালগরিদম দিয়ে n এর বর্গমূল পর্যন্ত সব প্রাইম বের করে p নামক অ্যারে তে রেখে দিয়েছি। এখন seg_sieve(); ফাংশনের শুরুতেই নির্দিষ্ট সেগমেন্টের লেন্থ বের করে mark অ্যারের সব ভ্যালু তে 0 বা false রাখতেছি। কারণ, শুরুতে ধরে নিব সব নাম্বারই প্রাইম। এরপর বর্গমূল R এর থেকে ছোট বা সমান প্রাইম গুলো দিয়ে তাদের মাল্টিপল গুলো কে 1 বা true দিয়ে মার্ক করে রাখতেছি। কারণ এগুলো কম্পোজিট। সবশেষে প্রাইম নাম্বারগুলো প্রিন্ট করে দিয়েছি।

আরেকটি বিষয় লক্ষণীয়, আমি উপরের কোডে সবজায়গায় int ব্যবহার করেছি কিন্তু কোথাও long long ব্যবহার করিনি। এর কারণ হচ্ছে n এর ভ্যালু int এর লিমিটের ভিতরেই আছে। সাধারণত সেগমেন্ট সিভ অ্যালগরিদম এর প্রয়োজন হবে এমন প্রবলেমে লিমিট অনেক বেশিই দেওয়া হয়। এই বিষয়টি নিয়ে একটু সতর্ক থাকলেই হবে। 

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

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

Prime Intervals
Help Hanzo
Prime Generator