প্রাইম নাম্বার বেসিক

প্রাইম নাম্বার বা মৌলিক সংখ্যা হল সেসব সংখ্যা যাদেরকে ১ এবং ঐ সংখ্যা ব্যাতিত অন্য কোন সংখ্যা দিয়ে নিঃশেষে ভাগ করা যায়না। অন্যভাবে বলতে গেলে , যেসব সংখ্যার মাত্র দুইটির বেশী ফ্যাক্টর/ভাজক থাকেনা তাদেরকে মৌলিক সংখ্যা বা প্রাইম নাম্বার বলে।
যেমন,  ৫ একটি প্রাইম নাম্বার কারন একে ১ এবং ৫ ব্যাতিত অন্য কোন সংখ্যা দিয়ে নিঃশেষে ভাগ করা যাবেনা। আবার এর ফ্যাক্টর  হল মাত্র দুটি (১,৫)। এরকম প্রাইম নাম্বারগুলো হল ২্‌,৩,৫,৭..
আবার যেসব সংখ্যা প্রাইম নাম্বার না তাদেরকে কম্পোজিট নাম্বার বলে। যেমন, ১০।  একে ১,২,৫,১০ ইত্যাদি দিয়ে ভাগ করা যায়।

প্রাইম নাম্বার চেকিংঃ
কোন নাম্বার প্রাইম নাম্বার কিনা তা চেক করতে সংজ্ঞাটি ব্যাবহার করা যেতে পারে। এইটা আমরা দুই ভাবে করতে পারি

১। ডিভাইজর হিসেব করেঃ আমরা জানি প্রাইম নাম্বারের ডিভাইজর ২ টার বেশী থাকেনা। তাহলে আমরা ১ থেকে শুরু করে ঐ সংখ্যা পর্যন্ত ভাগ করে দেখতে পারি। যদি ডিভাইজর দুইটার বেশী না হয় তাহলে সংখ্যাটি প্রাইম আর যদি বেশী হয় তাহলে সংখ্যাটি প্রাইম না। আচ্ছা, আমরা ঐ সংখ্যা পর্যন্ত ভাগ করছি কেন ? কারন সংখ্যাকে তার চেয়ে বড় সংখ্যা দ্বারা ভাগ করা যাবেনা। ৮ কে নিশ্চয়ই ৯ দ্বারা ভাগ যাবেনা তাইনা?

২। ১ বা ঐ সংখ্যা বাদে অন্য কোন সংখ্যা দিয়ে ভাগ করা যায় কিনা তা দেখেঃ এক্ষেত্রে আমরা ২ থেকে শুরু করে ঐ সংখ্যার আগের সংখ্যা পর্যন্ত ভাগ করে দেখতে পারি যদি ভাগ না যায় তাহলে সংখ্যাটি প্রাইম আর নাহলে প্রাইম না । সংখ্যাটি যদি ৮ হয় তাহলে আমরা ২ থেকে শূরু করে ৭ পর্যন্ত ভাগ করবো । প্রথমে নিজে কোড করতে চেষ্টা কর তারপর কোড দেখো ।

প্রথম পদ্ধতিঃ

 #include <stdio.h>  
 int main()  
 {  
   int n,i, count= 0;  
   scanf("%d", &n);  
   for(i= 1;i<= n;i++)  
   {  
     if(n%i == 0)  
       count++;  
   }  
   if(count == 2)  
     printf("Prime\n");  
   else  
     printf("Not prime\n");  
  return 0;  
 }  

দ্বিতীয় পদ্ধতিঃ

 #include <stdio.h>  
 int main()  
 {  
   int n,i, flag= 1;  
   scanf("%d", &n);  
   for(i= 2;i<n;i++)  
   {  
     if(n%i == 0)  
       {  
         flag= 0;  
         break;  
       }  
   }  
   if(flag == 1)  
     printf("Prime\n");  
   else  
     printf("Not prime\n");  
  return 0;  
 }  

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

 #include <stdio.h>  
 int main()  
 {  
   int n,i, flag= 1;  
   scanf("%d", &n);  
   for(i= 2;i<=n/2;i++)  
   {  
     if(n%i == 0)  
       {  
         flag= 0;  
         break;  
       }  
   }  
   if(flag == 1)  
     printf("Prime\n");  
   else  
     printf("Not prime\n");  
  return 0;  
 }  

সবই ঠিক রাখলাম শুধু n/2 পর্যন্ত ভাগ করলাম। এখন কথা হল এটাই কি পর্যাপ্ত ? N এর মান যদি ১০^২৫ বা তার উপরে হয়  তাহলে রেজাল্ট আসতে দিন লেগে যাবে। আর আমাদের প্রোগ্রামিং করাটাই বৃথা হয়ে যাবে।  প্রোগ্রামিং করার একটা কারন হল সময় বাঁচানো উলটো যদি সময়ের অপচয় হয় তাহলে প্রোগ্রামিং করে লাভ কি ? তখন সারাদিন এর পেছনে বসে থাকবে আর বলবে Programmer has no life. লাইফ তো মিয়া নিজেই ধ্বংশ করলা।

যাইহোক কাজের কথায় আসি, এর চেয়ে আরো  এফিসিয়েন্ট ওয়েতে আমরা করতে পারি। আমাদের আসলে n/2 পর্যন্ত ভাগ করার মোটেও প্রয়োজন নেই। কারন যেকোন সংখ্যার স্কয়ার রুট পর্যন্ত ভাগ করলে আমরা সকল ডিভাইজর পেয়ে যাই; তাহলে ডিভাইজর পাওয়ার জন্য n/2 পর্যন্ত ভাগ করার কি দরকার?
ধরা যাক একটি সংখ্যা ৬৪, এর ফ্যাক্টরগুলো বের করিঃ
৬৪/১ = ৬৪
৬৪/২ = ৩২
৬৪/৪= ১৬

উপর থেকে দেখা যাচ্ছে যে ৬৪ এর ফ্যাক্টরগুলো হল ১,২,৪,১৬,৩২,৩৬ । এই ফ্যাক্টরগুলো আমরা কিভাবে পেলাম? ১ থেকে ৪ সংখ্যা দিয়ে পর্যন্ত ভাগ করে। আর ৬৪ এর স্কয়ার  রুট হল ৪।

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

 #include <stdio.h>  
 #include <math.h>  
 int main()  
 {  
   int n,i, flag= 1;  
   scanf("%d", &n);  
   for(i= 2;i<=sqrt(n);i++)  
   {  
     if(n%i == 0)  
       {  
         flag= 0;  
         break;  
       }  
   }  
   if(flag == 1)  
     printf("Prime\n");  
   else  
     printf("Not prime\n");  
  return 0;  
 }  

এখন আমাদের টাইম sqrt(n) পর্যন্ত নেমে আসছে। যেটা ৫০০০০ এর যায়গায় হয়ে গেছে sqrt(১০০০০০)  যা ৩১৬ মিলিসেকেন্ড। আজ এ পর্যন্তই, দেখা হবে অন্য কোন সময়ে।