প্রাইম জেনারেশন সিভ ও প্রাইম ফ্যাক্টরাইজেশন

প্রাইম নাম্বার – নাম্বার থিওরীর রহস্যময় জগতে এক শৈল্পিক সৌন্দর্যের প্রতীক! প্রাইম নাম্বারের সৌন্দর্যের মোহে হাজার হাজার বছর ধরে গণিতবিদরা এ বিষয়ে গবেষণা করেছেন, নিত্যনতুন প্রাইম আবিষ্কারে উন্মুখ হয়েছেন। আর এখন যখন ইন্টারনেটের যুগ, ক্রিপ্টোগ্রাফির যুগ, তখন প্রাইম নাম্বার ব্যতীত কিছু ভাবাই যায় না। প্রাইম নাম্বারের এই অসীম সৌন্দর্যের সাগরে আজকে আমরা একটু পা ভেজাব মাত্র!

 

বাচ্চাকালের প্রশ্ন! প্রাইম নাম্বার কি? বাচ্চাদের মতই আধোআধো বোলে উত্তর দিয়ে দাও – প্রাইম নাম্বার হচ্ছে এমন একটি সংখ্যা যা ১ এবং ওই সংখ্যাটি ছাড়া অন্য কোন সংখ্যা দিয়েই নিঃশেষে বিভাজ্য নয়। অর্থাৎ কোন সংখ্যা প্রাইম কিনা সেটা জানার জন্যে ২ থেকে ওই প্রাইম নাম্বারের আগ পর্যন্ত সবগুলো সংখ্যা দিয়ে ওই সংখ্যাটি নিঃশেষে বিভাজ্য কিনা, সেটা দেখলেই হবে। কিন্তু এই পদ্ধতিটা অনেক ধীর গতিতে কাজ করে। মহান গণিতবিদেরা তাই দ্রুতগতিতে প্রাইম নাম্বার জেনারেট করার জন্য বিভিন্ন পদ্ধতি, বিভিন্ন অ্যালগোরিদম আবিষ্কার করেছেন। এর মধ্যে কনটেস্ট প্রোগ্রামিংয়ে সর্বাধিক ব্যবহৃত অ্যালগোরিদম হচ্ছে ‘Sieve of Eratosthenes’.

 

প্রাইম নাম্বারের সংজ্ঞাতেই বলা আছে – প্রাইম নাম্বার ১ এবং ওই সংখ্যা ব্যতীত অন্য কোন সংখ্যা দিয়ে নিঃশেষে বিভাজ্য নয়। এই কথাটার সহজ মানে হচ্ছে, কোন সংখ্যা যদি প্রাইম নাম্বার হয়, তাহলে ওই সংখ্যার কোন গুণিতক প্রাইম নাম্বার হতে পারবে না। অর্থাৎ ২ যদি প্রাইম নাম্বার হয়,  তাহলে ৪,৬,৮,১০,১২,….. সহ ২ এর কোন গুণীতকই প্রাইম নাম্বার হতে পারবে না। ৩,৫,৭,১১ এ সকল প্রাইম নাম্বারের ক্ষেত্রেও এই কথা সত্য।

 

এখন মনে প্রশ্ন জাগতেই পারে, আমাদের তো তাহলে আগে থেকে জানতে হবে, প্রাইম নাম্বার কোনগুলো! :-/ এজন্যেই আমরা একটি অ্যারে রাখব, যেখানে ভ্যালু থাকবে মাত্র দুটো, ০ আর ১.
এই অ্যারের ০,১ নির্দেশ করবে কোন সংখ্যাটি প্রাইম আর কোন সংখ্যাটি কম্পোজিট অর্থাৎ নন-প্রাইম।

 

কোড লেখার আগে এই ছবিটা দেখে কনসেপ্টটা ক্লিয়ার করে নাওঃ

 

Sieve of Eratosthenes

 

এবার তাহলে অ্যালগোরিদমটি ইমপ্লিমেন্ট করা যাক। প্রথমেই আমরা যত সংখ্যা পর্যন্ত প্রাইম বের করতে চাই, তত সাইজের একটা অ্যারে রাখব এবং অ্যারের প্রতিটি ইনডেক্সে ০ ভ্যালু রেখে দেব। এই ০ ভ্যালুই কোন সংখ্যার প্রাইমালিটি নির্দেশ করবে। প্রথমেই ২ এর সবগুলো গুণীতক ছেটে ফেলি-অর্থাৎ ২ এর গুণীতকের ইনডেক্সে ১ রেখে দেই। এবার ৩ থেকে যত সংখ্যা পর্যন্ত প্রাইম বের করতে চাই তত সংখ্যা পর্যন্ত একটা লুপ চালাব। যদি কোন সংখ্যার ইনডেক্সে ০ থাকে, তার মানে ওই সংখ্যাটি প্রাইম। তখন আরেকটি লুপ চালিয়ে ওই সংখ্যার সবগুলো গুণিতকের ইনডেক্সে ১ রেখে দেব। একদম শেষে যেসব নাম্বারের ইনডেক্সে ০ থাকবে, সেগুলোই আমরা কাঙ্ক্ষিত প্রাইম নাম্বার। চাইলে আমরা সেগুলোকে পরবর্তীতে ব্যবহারের জন্য কোন ভেক্টর কিংবা অ্যারেতে স্টোর করেও রাখতে পারি।

 

এখানে একটা ছোট্ট অপটিমাইজেশন আছে। আমরা ৩ থেকে যেই লুপটা চালাচ্ছি, সেই লুপটা আসলে আমাদের নির্ধারিত সীমা অর্থাৎ যেপর্যন্ত প্রাইম নাম্বার বের করতে চাচ্ছি, সে পর্যন্ত চালাতে হয় না। ওই নির্ধারিত সীমার বর্গমূল পর্যন্ত লুপটা চললেই সব প্রাইম নাম্বার আমরা পেয়ে যাব। কারণ, কোন সংখ্যাই তার বর্গমূলের থেকে বেশি দুটি সংখ্যার গুণফল হতে পারে না। কি, কনফিউজড?! 😕 ব্যাখ্যাটা আসলে খুবই সহজ।

 

ধরি, আমরা ১০০ পর্যন্ত সব প্রাইম নাম্বার বের করতে চাই। তো প্রথমেই আমরা নিয়মানুযায়ী ২,৩,৫,৭ এর গুণিতকগুলোর ইনডেক্সে ১ রেখে দেই। এরপরের প্রাইম নাম্বার হচ্ছে ১১, যা কিনা ১০০ এর বর্গমূল ১০ এর থেকে বেশি। স্বাভাবিকভাবেই আমরা ১১ এর গুণিতকগুলোর ইনডেক্সে ১ রাখতে যাব। কিন্তু একটু খেয়াল করলেই দেখবে, সেই সংখ্যাগুলোর ইনডেক্সে আগের থেকেই ১ আছে, কারণ আমরা ১১ এর চেয়ে ছোট প্রাইম ২,৩,৫,৭ এর ক্ষেত্রেই এই কাজটি করে রেখেছি। যেহেতু, ১১ * ১১ = ১২১ যা কিনা আমাদের নির্ধারিত সীমার বাইরে, তাই ১২১ কিংবা এর পরের গুণিতকগুলো বাদ দিয়ে আমাদের কোন লাভ নেই।

 

এইটুকুর কনসেপ্ট পুরোপুরি ক্লিয়ার হলে কোডটাও লিখে ফেলা যাক। তবে কোড দেখার আগে নিজে নিজেই একবার চেষ্টা করে দেখো।

 

#define MAX 1000005

int prime[MAX];
vector<int> p;

void sieve()
{
    memset(prime,0, sizeof(prime));
    prime[0]=prime[1]=1;
    for(int i = 4; i < MAX; i+= 2)
    prime[i] = 1;
    for(int i = 3; i*i < MAX; i+=2)
    {
        if(prime[i]==0)
        {
            for(int j = i*i; j < MAX; j+=i)
            prime[j]=1;
        }
    }
    for(int i = 2; i < MAX; i++)
        if(prime[i]==0)
            p.push_back(i);

}

 

প্রাইম জেনারেটর সিভের কোড নিজে নিজে লিখে ফেলতে পারলে প্রাইম ফ্যাক্টরাইজেশন বের করার কাজ ৯০% শেষ। কিন্তু এই প্রাইম ফ্যাক্টরাইজেশনটা আবার কি?? :/

 

যেকোন সংখ্যাকেই কতগুলো প্রাইম নাম্বারের গুণফল হিসেবে লেখা যায়। এটাকেই বলে প্রাইম ফ্যাক্টরাইজেশন। যেমন, ১২ কে লেখা যায় ২x২x৩, ৯০ কে লেখা যায়, ২x৩x৩x৫। প্রাইম ফ্যাক্টরাইজেশন অনেক গুরুত্বপূর্ণ কাজে ব্যবহৃত হয়। যেমনঃ কোন সংখ্যার কতগুলো ভাজক(Divisor) আছে, ক্রিপ্টোগ্রাফিতেও এর ব্যবহার প্রচুর।

 

আমরা তো আগেই প্রাইমগুলো একটা ভেক্টরে রেখে দিয়েছি। এবার তাহলে আমরা শুধু ভেক্টরের মধ্যে একটা লুপ ঘুরাব, আর দেখব, কোন কোন প্রাইম দিয়ে কোন সংখ্যা কতবার নিঃশেষে বিভাজ্য হয়। যদি ভাগ দিতে দিতে সংখ্যাটির মান ১ হয়ে যায়, তার মানে সংখ্যাটিকে আর কোন প্রাইম দিয়েই নিঃশেষে ভাগ করা যাবে না। আর যদি সব প্রাইম দিয়ে ভাগ করার পরেও সংখ্যাটির মান ১ না হয়, তাহলে বুঝতে হবে, ওই সংখ্যাটিই আরেকটি প্রাইম।

 

প্রাইম ফ্যাক্টরাইজেশনের কোডটা হবে এরকমঃ

 

for(int i = 0; i < p.size(); i++)
{
    while(n%p[i]==0)
    {
        n/=p[i];
        cout << p[i] << endl;
    }
    if(n==1)
        break;
}
if(n!=1)
    cout << endl;

 

লেখাটি আপাতত এখানেই শেষ। শেষ করার আগে একটা নিউরণ কাঁপানো সংবাদ দিয়ে যাই। জানুয়ারি, ২০১৬ তে GIMPS(Great Internet Mersenne Prime Search) নামক একটা সফটওয়্যারের মাধ্যমে এখন পর্যন্ত সবচেয়ে বড় প্রাইম নাম্বারটি আবিষ্কৃত হয়। প্রাইম নাম্বারটি হচ্ছে, 274,207,281 – 1 যার ডিজিট সংখ্যা 22,338,618. কল্পনায় আঁটছে না তো? যদি খুব ক্ষুদ্র অক্ষরে সংখ্যাগুলো লেখা হয়, তাহলে সংখ্যাটি প্রায় ১৩.৫ মাইল লম্বা হবে!!! 😮

 

‘শেষ হইয়াও হইল না শেষ।’ :p কনসেপ্ট পুরোপুরি ক্লিয়ার করতে নিচের প্রব্লেমগুলো সলভ করে ফেলো! 😀

406 – Prime Cuts (UVA)

10392 – Factoring Large Numbers (UVA)

11466 – Largest Prime Divisor (UVA)

Advertisements

2 thoughts on “প্রাইম জেনারেশন সিভ ও প্রাইম ফ্যাক্টরাইজেশন

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s