প্রাইম নাম্বার- সিভ অব এরাটস্থেনিজ

সিভ মানে হল ছাঁকনি। এই এলগোরিদমে কম্পোজিট নাম্বারগুলো থেকে প্রাইম নাম্বারগুলোকে ছেঁকে আলাদা করা হয়। আর গ্রিক গণিতবিদ এরাটস্থেনিজ (২৭৬ পূর্বাব্দ – ১৯৫ পূর্বাব্দ) এই এলগোরিদমের আবিষ্কারক বিধায় এলগোরিদমটির নাম দেওয়া হয়েছে সিভ অফ এরাটস্থেনিজ। দ্রুততার সাথে প্রাইম নাম্বার বের করার ক্ষেত্রে এলগোরিদমটি এতোটাই কার্যকর যে ২২০০ বছরের পুরোনো এই এলগোরিদম আজও কম্পিউটার বিজ্ঞানে ব্যবহার করা হয়। 

ছবিঃ উইকিপিডিয়া

সিভ দুইটি জিনিসের উপর ভিত্তি করে কাজ করেঃ 

১। যে যেকোন কম্পোজিট নাম্বার দুই বা ততোধিক প্রাইম নাম্বারের গুনফলের সমিষ্টি। যেমন, ৩৫ = ৩x৫ , ২১ = ৩x৭ ।  তার মানে হল সংখ্যাটি যদি n হয় তাহলে n  = p1 X p2 X p3....pk ।

২। আমরা জানি জানি, যেকোন কম্পোজিট সংখ্যা তার বর্গমূলের সমান বা ছোট অন্তত একটি সংখ্যা দিয়ে ভাগ যাবে। 

মনে কর, তোমার কাছে ১০০ টা বক্স আছে।  তোমাকে ১০০ পর্যন্ত প্রাইম নাম্বার বের করতে হবে। তুমি প্রত্যেকটা বক্সকে ০ থেকে ১০০ পর্যন্ত নাম্বারিং করলে। এখন তোমাকে শুধু নির্দেশ করতেই পারলেই হল যে কত নাম্বারের বক্সটি প্রাইম। সেক্ষেত্রে কি করবে? হুম; একটু ভাবো! আশাকরি তোমার ভাবা শেষ। নির্দেশ করার জন্য আমরা বক্সে কিছু  জিনিস রাখবো। সেটা যেকোন কিছু হতে পারে। আমরা ০ আর ১ ব্যাবহার করবো।  যদি সংখ্যাটি প্রাইম হয় তাহলে বক্সে ১ রাখবো আর যদি প্রাইম না হয় তাহলে বক্সে ০ রাখবো। প্রথমেই মনে কর, সবগুলো বক্স প্রাইম । তাহলে আমরা সবগুলো বক্সে ১ রাখলাম । বক্স হিসেবে আমরা int টাইপের একটা অ্যারে ১০১ সাইজের অ্যারে  নিলাম। 

 prime[101]  

এখানে ০ থেকে ১০০ পর্যন্ত prime নামের ১০০ টি বক্স তৈরী হয়ে গেছে। বক্সগুলো হল... 

 prime[0],prime[1], prime[2], prime[3]........prime[100]  ইত্যাদি

ইন্ডেক্সগুলো বক্সের নাম্বার হিসেবে কাজ করবে ভেরিয়েবলের ভেতরে আমরা ০/১ রাখবো। এখন মনে করি সবগুলো নাম্বার প্রাইম। তাহলে আমরা সবগুলো বক্সে ১ রাখবো।

 for(i= 0;i<=100;i++)  
   prime[i] = 1;  

এখন আমরা আস্তে আস্তে কম্পোজিট নাম্বারগুলো আইডেন্টিফাই করবো। আমরা আগে থেকেই জানি ০ এবং ১ প্রাইম নাম্বার না। তাহলে ০ এবং ১ এর যায়গায় ০ বসিয়ে দিতে পারি। 

 prime[0] = prime[1] = 0  

এবার আমরা জানি যে ২ ব্যাতিত বাকি সব জোড় সংখ্যাই কম্পোজিট নাম্বার। তাহলে নির্দ্বিধায় ২ ছাড়া বাকি জোড় সংখ্যাগুলোকে কম্পোজিট হিসেবে আইডেন্টিফাই করতে পারি। মানে, ওগুলোতেও শুন্য বসিয়ে দেবো।

 for(i= 4;i<=100;i= i+2)  
   prime[i] = 0;  

এইবার হল বাকি নাম্বারগুলোর ফালা। আমাদের এখন শুধু আইডেন্টিফাই করতে হবে বিজোড় কম্পোজিট সংখ্যাগুলোকে। আমরা আগে থেকেই জানি যেকোন কম্পোজিট সংখ্যা দুই বা ততোধিক প্রাইম নাম্বারের গুনফল! তাহলে প্রাইম নাম্বারের গুনফলগুলোও কম্পোজিট নাম্বার। এখন সেই কাজটাই করবো।

 for(i= 3;i<=sqrt(100);i++)  
 {  
    if(prime[i] == 1)  
    for(j= i*i;j<=100;j= j+i)  
 {  
   prime[j] = 0;  
 }  
 }  

কোডটি দেখলেই বুঝে ফেলার কথা কিভাবে কাজ করছে। প্রথমে ৩ কে প্রাইম ফেলো । তারপর ৩ সহ অন্যান্য যেসব প্রাইম  এর যে গুনফল আছে সেগুলোতে ০ বসিয়ে দিবে । ৯,১২,১৫,১৮... এভাবে সে সকল কম্পোজিট নাম্বার আইডেন্টিফাই করে ফেলবে। এখন যেসব সংখ্যা কম্পোজিট সেসব ঘরে ০ আছে বাকি বাকি ঘরগুলোতে ১ আছে। যেগুলোতে ১ আছে ওগুলোই কম্পোজিট নাম্বার।
এখন সম্পূর্ণ কোডটি লিখে ফেলিঃ

 #include <stdio.h>  
 #include <math.h>  
 int main(){  
  int prime[101],i,j,n;  

  for(i= 0;i<=100;i++)  
  prime[i]= 1;  

  prime[0]= prime[1]= 0 ;  

  for(i= 4;i<=100;i= i+2)  
  prime[i]= 0;  

  for(i= 3;i<=sqrt(100);i= i+2){  
   if(prime[i]==1){  
     for(j= i*i;j<=100;j= j+i){  
       prime[j]= 0;  
     }  
   }  
  }  

  for(i= 0;i<=100;i++){  
   if(prime[i]==1)  
     printf("%d ",i);  
  }  
 return 0;  
 }