এরাটস্থ্যানিজের সিভ

মৌলিক সংখ্যা

একটা সংখ্যা n কে আমরা মৌলিক সংখ্যা বলে ডাকতে পারি যদি সংখ্যাটাকে শুধু 1 আর n দিয়ে নিঃশেষে ভাগ করা যায়।

যেমন, ৫ একটা মৌলিক সংখ্যা কারণ আমরা ৫ কে শুধু ১ আর ৫ দিয়ে ভাগ করতে পারি কোন রকম ভাগশেষ না রেখে। আর কোন সংখ্যা দিয়ে ৫ কে ভাগ করা সম্ভব নয়। কিন্তু ৬ কি একটা মৌলিক সংখ্যা? উমম... নাহ!‍ ৬ কে আমরা ভাগ করতে পারি ১,২,৩ আর ৬ দিয়ে। তো সংজ্ঞা অনুযায়ী ৬ মৌলিক সংখ্যা নয়। ১ কে আমরা মৌলিক সংখ্যা হিসেবে বিবেচনা করি না।

যে কোন সংখ্যাকে কিছু মৌলিক সংখ্যার গুণফল হিসেবে ইউনিকভাবে প্রকাশ করা যায়। যেমন, ১২০=২৩×৩×৫। আবার, ৩৬=২২×৩২। আপনি যতই চেষ্টা করুন না কেন ৮,১২০ বা ৩৬ কে অন্য কোন মৌলিক সংখ্যার সেটের গুণফল হিসেবে প্রকাশ করতে পারবেন না। এভাবে চিন্তা করতে গেলে একেকটা সংখ্যাকে যদি আমরা একেকটা দেয়াল হিসেবে ভাবি, মৌলিক সংখ্যাগুলো হচ্ছে তাদের একেকটা ইট। বাকি সব সংখ্যাগুলো মৌলিক সংখ্যার উপর ভিত্তি করে বানানো।

মৌলিক সংখ্যাকে ইংরেজিতে প্রাইম নাম্বার (prime number) বলে। আমরা এখন থেকে মৌলিক সংখ্যাকে প্রাইম নম্বর ডাকবো।

এরাটস্থ্যানিজের সিভ

আমরা যদি n পর্যন্ত সবগুলো মৌলিক সংখ্যা বের করতে চাই, আমরা হয়তো এরকম একটা কোড লিখবো (আমি পুরো কোড আর সবগুলো হেডার ইচ্ছা করে লিখিনি - শুধু দরকারি অংশে মনোযোগ দেয়ার জন্য)। কোড লিখার জন্য C++ আমরা ব্যাবহার করবো। C++ এর STL সম্পর্কে জানতে চাইলে এখানে থেকে পড়তে পারেন।

#include <vector>


using namespace std;




vector<int> getPrimes(int n) {

    vector<int> primes;

    for (int i = 2; i <= n; i++) {


        if (isPrime(i)) {


        primes.push_back(i);

        }


    }



    return primes;


}

এটার টাইম কম্প্লেক্সিটি হচ্ছে O(n√n)। আমরা এটাকে আরো ফাস্ট করতে পারি এরাটস্থ্যানিজের সিভ (Sieve of Eratosthenes) ব্যবহার করে, যেটার টাইম কম্প্লেক্সিটি হচ্ছে O(nlog(log(n)))। টাইম কম্প্লেক্সিটি সম্পর্কে জানতে চাইলে এই লিখাটি পড়তে পারেন। আমি এখন যেই অ্যালগরিদমটা শেখাবো সেটা দুই হাজার বছর পুরনো! 

এরাটস্থ্যানিজের সিভ খুব সহজ একটা অ্যালগরিদম। আমি n পর্যন্ত সবগুলো সংখ্যা লিখবো। তারপর একটা একটা করে সংখ্যা নিবো ছোট থেকে বড় অর্ডারে, যদি সেটা অলরেডি কাটা না হয় তাহলে ওটার সবগুলো মাল্টিপলকে কেটে ফেলবো। যেমন, যদি আমরা ২ পাই আমরা ২,৪,৬,৮,১০,১২,১৪,১৬,…,২ কে কেটে ফেলবো। কারণ ২ এদের সবাইকেই তো নিঃশেষে ভাগ করতে পারে, সুতরাং এদের কারোই প্রাইম হবার ক্ষমতা নাই।

 আমরা যদি ছোট থেকে বড়তে যেতে যেতে এমন একটা সংখ্যা পাই যেটাকে এখনো কাটা হয় নাই, তাহলে তার মানে দাঁড়াচ্ছে আমরা এমন কোন সংখ্যা খুঁজে পাইনি যেটা ওই সংখ্যাটার চেয়ে ছোট এবং ওকে নি:শেষে ভাগ করতে পারে। তার মানে সেটা একটা প্রাইম নম্বর!

© wikipedia

  সাধারণ ইম্প্লিমেন্টেশন

#define M 1000000



bool marked[M];


void sieve(int n) {


    for (int i = 2; i < n; i++) {



        if (marked[i] == false) { // i is a prime



            for (int j = i + i; j <= n; j += i) {

               marked[j] = true;

           }

        }



    }


}

এই অংশটুকু সব কম্পোজিট নাম্বারগুলোকে মার্ক করে রাখবে এরাটস্থ্যানিজের অ্যালগরিদম অনুযায়ী । তো শুধু প্রাইম নাম্বারগুলো false হয়ে থাকবে marked অ্যারেতে।

আমরা আমাদের isPrime নতুন করে লিখতে পারি এভাবে।

bool isPrime(int n) {


    if (n < 2) return false;



    return marked[n] == false;


}

sieve এর প্রথম লুপটা কিন্তু n পর্যন্ত চালানো প্রয়োজন নেই। মনে আছে, আমরা প্রমাণ করেছিলাম প্রতিটা সংখ্যার একটা ডিভিজর থাকবে যেটা √n সমান অথবা ছোট হবে? তো কোন সংখ্যা যদি প্রাইম না হয় তাহলে √n সমান বা ছোট একটা সংখ্যা সেটাকে এমনিই মার্ক করবে। সেজন্য আমরা প্রথম লুপটা √n চালালেই পারি। একই ব্যাপারটা ভেতরের লুপের জন্যও সত্যি। কেও যদি মার্ক করার হয় সেটা √n এর মধ্যেই মার্কড হবে। তো আমরা ২ থেকে শুরু না করে ২ থেকে শুরু করতে পারি।

#define M 1000000


bool marked[M];


void sieve(int n) {


    for (int i = 2; i * i <= n; i++) {



        if (marked[i] == false) { // i is a prime

            for (int j = i * i; j <= n; j += i) {



                marked[j] = true;

           }

        }



    }


}

আবার খেয়াল করুন আমরা বারবার ২ এর মাল্টিপলদের মার্ক করছি। যেমন, যখন ২ এর মাল্টিপলদের মার্ক করছি তখন আমরা আসলে মার্ক করছি ৬,৯,১২,১৫,১৮,...৩। যাদের অর্ধেক হচ্ছে ২ এর মাল্টিপল। একই কথা বাকি সব প্রাইম নম্বরদের জন্য সত্য। আমরা সেটা এড়াতে পারি শুধু অড মাল্টিপলগুলোকে মার্ক করে।

#define M 1000000


bool marked[M];


bool isPrime(int n) {


    if (n < 2) return false;



    if (n == 2) return true;



    if (n % 2 == 0) return false;



    return marked[n] == false;


}





void sieve(int n) {


    for (int i = 3; i * i <= n; i += 2) {



        if (marked[i] == false) { // i is a prime



            for (int j = i * i; j <= n; j += i + i) {



                marked[j] = true;



            }



       }



    }


}