অ্যালগরিদম - Algorithmsসংখ্যাতত্ত্ব - Number theory

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

Prime number algorithm Bangla tutorial/ Sieve of Eratosthenes

অনেকদিন লেখালেখি থেকে দুরে ছিলাম। আজকে লিখতে বসলাম কিন্তু টপিক পাচ্ছিলাম না। ভেবে চিন্তে মনে হলো মৌলিক সংখ্যা বা প্রাইম নাম্বার (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 ইনডেক্সে  গিয়ে চেক করবেন  যে এটা শূন্য না ১ । ১ হলে প্রইম নাম্বার । না হলে নাই ।

  1. // C++ program to print all primes smaller than or equal to
  2. // n using Sieve of Eratosthenes
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. void SieveOfEratosthenes(int n)
  7. {
  8.     // Create a boolean array “prime[0..n]” and initialize
  9.     // all entries it as true. A value in prime[i] will
  10.     // finally be false if i is Not a prime, else true.
  11.     bool prime[n+1];
  12.     memset(prime, true, sizeof(prime));
  13.  
  14.     for (int p=2; p*p<=n; p++)
  15.     {
  16.         // If prime[p] is not changed, then it is a prime
  17.         if (prime[p] == true)
  18.         {
  19.             // Update all multiples of p greater than or 
  20.             // equal to the square of it
  21.             // numbers which are multiple of p and are
  22.             // less than p^2 are already been marked. 
  23.             for (int i=p*p; i<=n; i += p)
  24.                 prime[i] = false;
  25.         }
  26.     }
  27.  
  28.     // Print all prime numbers
  29.     for (int p=2; p<=n; p++)
  30.        if (prime[p])
  31.           cout << p << ” “;
  32. }
  33.  
  34. // Driver Program to test above function
  35. int main()
  36. {
  37.     int n = 30;
  38.     cout << “Following are the prime numbers smaller “
  39.          << ” than or equal to ” << n << endl;
  40.     SieveOfEratosthenes(n);
  41.     return 0;
  42. }

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

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

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

লেখাটি কেমন লেগেছে আপনার?

রেটিং দিতে হার্টের উপর ক্লিক করুন।

গড় রেটিং / 5. মোট ভোট:

আপনি প্রথম ভোটদাতা.

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

8 টি মন্তব্য

  1. Bit field দিয়ে কিভাবে Eratosthenes Sieve C language এ implement করা যায় তার ওপর একটি পোস্ট থাকলে ভালো লাগতো

  2. শেষের কোডের prime array main() function থেকে ব্যাবহার করা যাবে কি??

    memset এর complexity কত??

    vector prime(n+1,1);
    এইটা আর memset এর মধ্যে কোন টা ভালো???

    1. হুম, প্রাইম এরে মেইন এ ডি‌ক্লেয়ার করা যা‌বে। সে‌ক্ষে‌ত্রে এ‌রের রেফা‌রেন্স প‌য়েন্টার আকা‌রে পাঠা‌নো লাগ‌বে।
      memset এর ক‌ম‌প্লে‌ক্সি O(N) থে‌কে বে‌শি হওয়ার কথা না। vector fill করার ক‌ম‌প্লে‌ক্সি‌টিও সমান।

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button