Sieve of Eratosthenes in O(n)

সিভ নিয়ে ফয়সালের এই লেখা পড়লে,কন্সেপ্ট বুঝতে সুবিধা হবে ।

কোনো সংখ্যাকে ১ এবং ঐ সংখ্যা ছাড়া আর কোনো সংখ্যা দ্বারা ভাগ করা না গেলে , সংখ্যাটা প্রাইম নাম্বার, আর যদি ভাগ যায় তাহলে সেটা কম্পজিট নাম্বার. একটা নাম্বার প্রাইম কিনা সেটা জানার জন্য প্রচলিত একটা পদ্ধতি হচ্ছে Eratosthenes sieve. এখানে করা হয় কী? প্রথমে ধরে নেওয়া হয়, প্রত্যেকটা নাম্বার হচ্ছে প্রাইম. একটা নাম্বার প্রাইম হলে তার গুনিতক সবগুলোকে প্রাইম এর লিস্ট থেকে বের করে দেওয়া হয়. এরপর পরবর্তী প্রাইম নাম্বার এ যাওয়া হয়, একইভাবে সেই প্রাইম নাম্বার এর গুনিতক সবগুলকে প্রাইম এর লিস্ট থেকে বের করে দেওয়া হয়. দিনশেষে যারা বাদ যাবে না, তারাই প্রাইম নাম্বার. কিন্তু এভাবে করার অসুবিধা হচ্ছে, একটা নাম্বার যদি প্রাইম না হয়, তাহলে তার সবগুলোও প্রাইম ফ্যাক্টর এর জন্য নাম্বারটা বারবার চেক হয়. এতে টাইম কমপ্লেক্সিটি বেড়ে যায়. তার চাইতে আমরা যেটা করতে পারি, কোনো নাম্বার যদি কম্পজিট হয়, তাহলে তার সবচেয়ে ছোট প্রাইম ফ্যাক্টর এর জন্য একবার সংখ্যাটাকে প্রাইম এর লিস্ট থেকে বাদ দেব. প্রথমে ধরে নেব প্রতেকটা সংখ্যা প্রাইম. এরপর 2 থেকে শুরু করে n পর্যন্ত প্রত্যেকটা নাম্বার এর জন্য কম্পোজিট নাম্বার জেনারেট করবো. বাদবাকি যেগুলো পড়ে থাকবে, সেগুলো হবে আমাদের প্রাইম নাম্বার.

ধরলাম একটা সংখ্যা q = x * p. যেখানে p হলো smallest prime factor যেটা কিনা q কে divide করে. তাহলে p ≤ x.

এখানে আমাদের মেইনলি দুইটা বিষয়ে ফোকাস করতে হবে. একটা হচ্ছে, x এর থেকে ছোটো সব প্রাইম নাম্বার জেনারেট হলো কিনা(আসলে চেক করবো কম্পোজিট নাম্বার জেনারেট হইছে কিনা) আরেকটা হলো x এর জন্য কোন কোন প্রাইম নাম্বার নিয়ে কম্পোজিট নাম্বার বানাবো. সেকেন্ডটা নিয়েই কথা বলি আগে.

আমরা প্রত্যেক x এর জন্য x পর্যন্ত যতগুলো প্রাইম আছে (কাদের কাদের নেব সেটা পরে বলছি) তাদের x এর সাথে গুন গিয়ে কম্পজিট নাম্বার তৈরী করব. আমাদের উদ্দেশ্য হচ্ছে, x এর সাথে প্রাইম নাম্বারটা গুন দিলে, যেই কম্পজিট নাম্বার তৈরী হয়, প্রাইমটা সেই কম্পজিট নাম্বার এর সবচাইতে ছোট ফ্যাক্টর. কোনো প্রাইম নাম্বার যদি x কে ডিভাইড করে, আমরা ঐ x কে ঐ প্রাইম এর পরের কোনো প্রাইম নাম্বার এর সাথে গুন করে কম্পোজিট নাম্বার বানাতে পারব না. কেন সেটা?

ধরলাম x এর সাথে p এর পরবর্তী প্রাইম নাম্বার p’ গুন করে, আমরা নতুন কম্পোজিট নাম্বার বানালাম q’ = x * p’. এখন যেহেতু x p দিয়ে ভাগ যায়,তারমানে q’ p দিয়ে ভাগ যায়। আর p < p’ তাহলে নতুন যে কম্পোজিট নাম্বার হবে, সেটার সবচাইতে ছোটো প্রাইম ফ্যাক্টর p’ হতে পারবে না।

x পর্যন্ত প্রাইম নাম্বার সব জেনারেট হবে, এটার সিউরিট কিভাবে দেব? আমরা শুরুতেই ধরে নিয়েছি সবগুলো সংখ্যা প্রাইম. x পর্যন্ত সবগুলো কম্পোজিট নাম্বার জেনারেট হইছে মানেই বাকিগুলো প্রাইম নাম্বার। x এর থেকে ছোটো কম্পজিট নাম্বার যদি i হয়, তাহলে এটি জেনারেট হতে যে সংখ্যা লাগবে সেগুলো অবশই x এর থেকে ছোট.

কোডটা হবে অনেকটা এরকম

vector<int>primes;
bool isComposite[maxi]; // as it is globally delclared, every element will become 0

void sieve (int n) {
isComposite[1] = true;
for (int i = 2; i < n; i++) {
if (isComposite[i] == 0) primes.push_back (i);
for (int j = 0; j < primes.size () && i * primes[j] < n; j++) {
            isComposite[i * primes[j]] =true;
if (i % primes[j] == 0)break;
        }
    }
}

ভেতরের লুপ প্রত্যেক কম্পজিট নাম্বার এর জন্য কেবল একবার চলবে তাই এর কমপ্লেক্সিটি হবে O(n).