মৌলিক সংখ্যা (Prime number) এর অ্যালগরিদম গুলো

অনেকদিন লেখালেখি থেকে দুরে ছিলাম। আজকে লিখতে বসলাম কিন্তু টপিক পাচ্ছিলাম না। ভেবে চিন্তে মনে হলো মৌলিক সংখ্যা বা প্রাইম নাম্বার (Prime Number) নিয়ে লিখবো। মৌলিক সংখ্যা হলো বিভিন্ন অ্যালগরিদম এর প্রাণ ভোমরার মতো।

প্রাইম ফ্যাক্টরাইজেশন নিয়ে জানতে এটা দেখুনঃ সংখ্যাতত্ত্ব: মৌলিক সংখ্যা (prime number) ও তার অ্যালগরিদম

 

তাহলে , প্রাইম নাম্বার আসলে কি ? সহজ হিসাব , ১ এ থেকে বড় যে সংখ্যা কে ১ আর ঐ সংখ্যা ছাড়া অন্য কোন সংখ্যা ছাড়া ভাগ যায় না তাই প্রাইম নাম্বার । এখন যদি বলা হয় N একটি নাম্বার । আপনাকে বলা হলো এটা প্রাইম কিনা তার একটি প্রোগ্রাম লিখতে ।
এর সমাধানটা তো মুটামুটি সংজ্ঞা থেকেই করা যা । একটি ৩ থেকে N-1 পর্যন্ত একটা লুপ নিয়ে ঐ সংখ্যা কে ভাগ করে যেতে হবে । যাদি ভাগ যায় তবে প্রাইম না । নাহলে প্রাইম নাম্বার । খুব সহজ ।

1. int i;
   
2. for(i=3;i<=n-1;i++)
   
3. {
   
4.      if(N%i==0)
   
5.      {
   
6.            printf(“NOT PRIME!”);
   
7.            return 0;
   
8.       }
   
9. }
   
10. printf(“PRIME!!”);

হলো । কিন্তু এখানে একটা সমস্যা আছে । ধরেন সংখ্যাটা  10^10 থেকে বেশি । তখন আপনি কি করবেন । ওপরে যেই প্রোগ্রামটা দেয়া হয়েছে তার টাইম কমপ্লেক্সিটি O(N) । মানে এটা একটা নাম্বার প্রইম কি না তা খুজতে সবচেয়ে বাজে কেসে N বার ঘুরবে । যখন আপনি N = 10^10 দিবেন তখোন 10^10 বার লুপ ঘুরা অসম্ভব কিছু নয় । কিন্তু যখন আপনাকে সমাধানটা করতে একটা নির্দিষ্ট সময় বেধে দেয়া হবে তখন ?? ধরেন আপনাকে সময় দিল ১ সেকেন্ড । কিন্তু এই ক্ষেত্রে ১ সেকেন্ডের বেশি নিবে উপরের প্রোগ্রাম টা । সুতরাং TLE িনশ্চিত।

এখন এই সমস্যার একটা সমাধান করা দরকার যা আরও কম সময় নিবে । তাহলে কি করা যায় ?
এখন , আমরা যদি কোন সংখ্যা N=50 এর গুনণীয়ক গুলো খেয়াল করি তবে দেখি একটি গুনণীয়ক d হলে ওপর গুনণীয়ক N/d । সুতরাং আমরা যদি N এর গুনণীয়ক গুলোকে ওপরের শর্তানুযায়ী সাজাই তবে , গুনণীয়ক গুলো হয় ,
(1,50) (2,25) (5,10)  যার সাধারন রূপ হলো (d,N/d)
লক্ষ করলে দেখা যায় প্রত্যেক জোড়ার ছোট নম্বারটা সবসময়ই √N এর ছোট বা সমান । কেন তা প্রমান করতে প্রথমে আমরা ধরে নেই দুইটাই √N এর চেয়ে বড় ।
সুতরাং,
a×b = N হওয়ার কথা ।
যেখানে a,b দুইটা গুনণীয়ক এবং a,b>√N ।
কিন্তু √N×√N = (√N)² = N
সুতরাং a,b এর দুইটাই √N এর বড় হতে পারে না । সুতরাং জোড়ার একটা গুনণীয়ককে অবশ্যই √N এর সমান বা ছোট হতে হবে ।

সুতরাং ওপরের প্রোগ্রাম এর একটি Efficient রূপ হলো ,

1. long long i;
2.  
3. for(i=2;i<=sqrt(N);i++)
4.  
5. {
6.  
7.      if(N%i==0)
8.  
9.      {
10.  
11.            printf(“NOT PRIME!”);
12.  
13.            return 0;
14.  
15.       }
16.  
17. }
18.  
19. printf(“PRIME!!”);

এই প্রোগ্রামটা √N লুপ ঘুরেই প্রাইম নাম্বার বের করতে পারবে ।

কিন্তু এখন আরেকটা সমস্যা এসে দাড়ালো ।
যদি বলা হয় ১০০০০০ বার তোমার প্রোগ্রামকে প্রশ্ন করা হবে এবং প্রতিবার তোমাকে একটা নাম্বার দেয়া হবে যেটা হবে 10^7 এর সমান বা ছোট । তবে আপনি কি করবেন ? প্রতিবার লুপ ঘুরিয়ে বের করবেন নাম্বারটা প্রাইম কিনা ? কিন্তু ধরেন আপনাকে এবার সম দিলো ২ সেকেন্ড । তবুও এবার আপনার TLE খেতে হবে । কারন সবচেয়ে বাজে কেসে আপনার 10^5Х10^4 = 10^9 বার লুপ ঘুরবে । সুতরাং কি করা যায় তবে । এই সমস্যাটা সমাধান করতে হবে যে ‍উপায়ে তার নাম সিভ অব ইরাটোসথেন্স ।
এখানে যা করা হয় তা হলো , একটা বুলিয়ান অ্যারে নিবো N+1 সাইজের । প্রথমেই অ্যারের ইলিমেন্টকে ১ করে দিবো । একটা লুপ ঘুরবো i = ২ থেকে i = √N পর্যন্ত । এর মাঝখানে আরেকটা লুপ নিবো j = 2*i থেকে j =N  পর্যন্ত । মাঝখানের লুপকে ইনক্রিমেন্ট করবো j+=i এভাবে । মানে প্রতিবারে j হবে i এর একেকটা গুণিতক । আমরা গুনিতক গুলোকে ০ করে দিবো । এইলুপটা ঢুকার আগে যা করতে হবে তা হলো দেখতে হবে নাম্বার টা আগেেই ০ হয়ে গেছে নাকি । যদি আগেই শূন্য হয়ে যায় তবে আর লুপ ঘুরানের মানে নেইঃ

এখন আপনি যা করবেন তা হলো নম্বার N ইনপুট নিবেন আর অ্যারে N ইনডেক্সে  গিয়ে চেক করবেন  যে এটা শূন্য না ১ । ১ হলে প্রইম নাম্বার । না হলে নাই ।

কোড ক্রেডিট : গিকস ফর গিকস

অতপর অ্যালগরিদম নিয় আরো কিছু লেখা লিখবো । সুতরাং সাথেই থকুন । কোন সমস্যা হলে কমেন্ট বক্সে কমেন্ট করুন

আরও পরুনঃ সংখ্যাতত্ত্ব: মডুলার অ্যারিথমেটিক (Modular arithmetic); Big mod