প্রাইম জেনারেটর (সিভ অফ এরাটোস্হেনেস)
আমার সবচেয়ে পছন্দের অ্যালগোরিদম এটি। একটা নির্দিষ্ট রেঞ্জের মধ্যের সব প্রাইম নাম্বার(মৌলিক সংখ্যা) বের করার জন্য সবচেয়ে প্রাচীন এবং ইফিশিনেন্ট পদ্ধতি এটি। এই পোস্টে আমি কিভাবে অ্যালগোরিদম টা ইম্প্লিমেন্ট করতাম এই নিয়ে একটু লেখার চেষ্টা করব।
যাই হোক এটি আবিষ্কার করেছিলেন তৎকালীন সময়ের স্যামওয়েল টার্লি :) । তিনি ছিলেন প্রাচীন গ্রিক আমলের আলেকজান্দ্রিয়া লাইব্রেরির প্রধান লাইব্রেরিয়ান। তিনি ছিলেন একাধারে একজন বিজ্ঞানী,কবি,লাইব্রেরিয়ান,গণিতবিদ। তাঁর জন্ম খ্রিস্টপূর্ব ২৭৬ এ। এরাটোস্হেনেস নাম্বার থিওরীতে তাঁর এই ছাকনি অাবিস্কারের জন্য বিখ্যাত।
সিভ দেখার আগে প্রাইম নাম্বার কি জিনিস সেটা অাগে দেখি। বলা হয় ১ এর চেয়ে বড় যে সকল সংখ্যার ১ এবং ঐ সংখ্যা ছাড়া কোন ধনাত্মক গুণনীয়ক(ডিভিসর) নেই তারা হচ্ছে প্রাইম যেমন: ৩,৫,৭,১১ ।
তো এই সংজ্ঞানুসারে প্রাইম নাম্বার বের করার জন্য আমরা কি করতে পারি। একটা সংখ্যা নেব তারপর ২ থেকে ঐ সংখ্যার আগের সংখ্যা পর্যন্ত সব সংখ্যাগুলো দিয়ে ভাগ করে দেখবো ভাগ যায় কিনা। ভাগ করা না গেলে প্রাইম গেলে নন প্রাইম।
তো একটা নির্দিষ্ট রেঞ্জের মধ্যে এই প্রসেস চালাতে গেলে 0(n²) টাইম কম্প্লেক্সিটির কারণে আমরা অনেক সময় ব্যয় করে ফেলব। আমাদের আরো ফাস্টার প্রসেসিং করা দরকার।
সিভ অফ এরাটোস্হেনেস যেটা প্রোপোস করে তা হলো : একটা রেঞ্জের মধ্যে প্রথম ধেকে শুরু করে যে কম্পজিট নাম্বার গুলো পাওয়া যাবে তাদের কেটে দিব। কম্পজিট নাম্বার হচ্ছে প্রাইম নাম্বারের গুণিতকগুলো। কাটাকাটি শেষ হলে যে নাম্বারগুলো পড়ে থাকবে তারাই হলো প্রাইম। উইকির এই ইমেজটা উদাহরণ দেবার জন্য অনেক চমৎকার:
এখানে যে কাজটা করা হয়েছে : প্রথম যে নাম্বারটা পাবো যা এখনো কাটাকাটি হয়নি তার সব গুণিতকগুলোকে কেটে দিব। এবং ঐ সংখ্যাটাকে প্রাইম হিসেবে স্টোর করবো।
তাহলে এখন কোডটা দেখি:
#define MAX 500
int arr[MAX];void sieve(){
//filter all 2's multiple
for(int a=4; a<MAX; a+=2)arr[a]=1; for(int a=3; a<MAX; a+=2)
{
//filter all multiple of 3,5,7,....
for(int b=a*2; b<MAX; b+=a)
arr[b]=1;
}
}
এখানে প্রথম লুপে আমরা সব জোড় সংখ্যাগুলোকে কেটে দিলাম। জোড় ইন্ডেক্স গুলা 1 বানালাম আর কি। 1হলে বলবো কাটা আর 0 হলে বলবো কাটা হয়নি।
তাহলে দ্বিতীয় লুপ টাতে এবং ইনার লুপে আমরা বিজোড় সংখ্যাগুলো নিচ্ছি আর তার গুণিতকগুলোকে কেটে দিচ্ছি। সবশেষে আমরা চেক করে দেখবো অ্যারের কোন ইন্ডেক্সগুলোতে 0 আছে। 0 ভাল্যুুওয়ালা ইন্ডেক্সগুলোই প্রাইম।এটা 0(n²) থেকে অনেক ফাস্টার।
এখন একটা একটা প্রবলেম সল্ভ করি: আমাদের বলা হলো একটা সংখ্যাকে সমান দুটো সংখ্যার গুনফল আকারে লেখতে হবে দুটো সংখ্যা কি হবে? উত্তরটা হলো ঐ সংখ্যার বর্গমূল। মানে a=√a* √a ।
এখন যদি বলি এইদুটো সংখ্যার যেকোন একটাকে একটু বাড়ায় দেবো তাহলে অবশ্যই অন্যটাকে একটু কমায় দিতে হবে।ব্যাপারটা দাঁড়ালো একটা সংখ্যার গুননীয়ক গুলোর মধ্যে অন্তত একটা অবশ্যই ঐ সংখ্যার বর্গমূলের সমান বা ছোট হবে। হাইস্কুল বা প্রাইমারীতে এই প্রমাণটা ছিল। এটা কাজে লাগাবো এখন। এখানে অামরা 500 এর নিচের সংখ্যাগুলোর গুননীয়ক চেক করছি তাহলে আমাদের দ্বিতীয় লুপটা √500≈25 পর্যন্ত চালালেই হবে। অলরেডি অনেক ফাস্ট হলো অ্যালগোটা
এখন আসি ইনারলুপ টাতে এখানে আমরা a এর প্রথম গুণিতক অর্থাৎ a*2 থেকে শুরু করেছি। কিন্তু আমরা তো 2 এর সব গুনিতক আমাদের প্রথম লুপে কেটে এসেছি । মূলত আমাদের শুরু করতে হবে a*a থেকে (more fast)। তাহলে a যদি 3 হয় আমাদের ইনার লুপ কাটাকাটি করবে 9,12,15,18,21, . . . . .
দেখা যাচ্ছে আবার আমরা জোড় ইন্ডেক্স এক্সেস করছি(12,18, . . .) কোন দরকার নেই b+=a করার কারণ বিজোড় এর সাথে বিজোড় যোগ করার কারণে জোড় ইন্ডেক্স এক্সেস হচ্ছে। তাহলে কি করবো? বিজোড় এর সাথে a এর প্রথম জোড় গুণিতক ( a*2) যোগ করবো। আরো ফাস্ট হলো ইনার লুপ।
for(int b=a*a; b<MAX; b+=a*2)আরো কি একটু ফাস্ট করা যায়? হুমমম যায় ভাই। কম্পিউটার জেনারেল অপারেশন এর চেয়ে বিটওয়াইজ অপারেশনগুলো একটু ফাস্ট করতে পারে । তাই উপরের ফরলুপে a*2 এর জায়গায় আমরা a<<1 করে aএর ভ্যালু ডাবল করবো। লেফ্ট শিফ্ট অপারেশন করলে সংখ্যার ডানে একটা এক্সট্রা 0 এ্যাড হয়। দশমিক নাম্বার সিস্টেমে যেমন সংখ্যার শেষে 0 দিলে সংখ্যা 10 গুণ হয় বাইনারীতে হয় 2 গুণ।
তাহলে আমাদের সুপার ফাস্ট অ্যালগো দাঁড়ালো এমন:
#define MAX 500
int arr[MAX];
void sieve(){
for(int a=4; a<MAX; a+=2)arr[a]=1;
int temp=sqrt(MAX); for(int a=3; a<=temp; a+=2)
{
for(int b=a*a; b<MAX; b+=a<<1)arr[b]=1;
}
}int main(void){
sieve();
for(int a=2; a<MAX; a++)
{
if(!arr[a])cout<<a<<" ";
}
}
আরো কি একটু ফাস্ট করা যায়?থাক আমাদের কারোরই পড়ার বা লেখার ধৈর্য আশা করি অবশিষ্ট নেই।শুনছি সিভ অফ অ্যাটকিন্স 0(n) এ কাজ করে।
যাই হোক এটার কম্প্লেক্সিটি O(n log log n)।
আর এতদূর পর্যন্ত পড়ে থাকলে অনেক ধন্যবাদ ☺️
(Also published at my personal blog)
