ডেটা স্ট্রাকচার ও অ্যালগরিদম/সীভ অব ইরাটোসথেন্স

সীভ অব ইরাটোসথেন্স হলো যে কোনও নির্দিষ্ট সীমা পর্যন্ত সব মৌলিক সংখ্যা খুঁজে বের করার জন্য ব্যবহৃত একটি প্রাচীন অ্যালগরিদম। মৌলিক সংখ্যা খুজে বের করার জন্য আমরা এর গুণনীয়ক বের করি। যদি কোনো সংখ্যার ১ এবং ঐ সংখ্যা বাদে অন্য কোনো গুণনীয়ক পাওয়া যায় তাহলে সেই সংখ্যাকে আমরা মৌলিক সংখ্যা বলি না। যদি একটু উল্টোভাবে চিন্তা করি, তাহলে কোনো একটি সংখ্যার গুণিতক কখনও মৌলিক সংখ্যা হতে পারে না। যেমন ধরা যাক ২ এর গুণিতক হলো ৪, ৬, ৮, ১০ ইত্যাদি। এই সব সংখ্যাগুলোই ২ দ্বারা বিভাজ্য, তাই এরা মৌলিক সংখ্যা নয়। সীভ অব ইরাটোসথেন্স অ্যালগরিদমেও মূলত এই বিষয়টিই ব্যবহার করা হয়। সীভ অব ইরাটোসথেন্স অ্যালগরিদম ব্যবহার করে কোনো একটি সীমার মধ্যে কতোগুলো সংখ্যা আছে এবং সংখ্যাগুলো কি কি তা আমরা বের করে ফেলতে পারি।

সীভ অব ইরাটোসথেন্স এর কোড যদি আমরা লেখি তাহলে সেটা হবে নিচের কোডের মতো

int primeCheck[1000001];

void sieveofEratosthenes(int n) {
    primeCheck[1] = 1;
    for (int i=4; i<=n; i+=2) {
        primeCheck[i] = 1;
    }
    for (int i=3; i<=n; i+=2) {
        if (i*i <= n) {
            for (int j=i*i; j<=n; j += i*2) {
                primeCheck[j] = 1;
            }
        }
    }
}