[প্রোগ্রামিং বইঃ অধ্যায় দশ] মৌলিক সংখ্যা।

মৌলিক সংখ্যা (Prime Number) গণিতবিদদের কাছে যেমন প্রিয়, তেমনই প্রোগ্রামারদেরও অনেক প্রিয় একটি বিষয়। তোমাদের বিভিন্ন সময়ে এই মৌলিক সংখ্যাসংক্রান্ত নানা সমস্যার সমাধান করতে হবে। মৌলিক সংখ্যা জিনিসটি যে গুরুত্বপূর্ণ সেটি বোঝার আরেকটি উপায় হলো, এই বইতে বিষয়টির জন্য আমি একটি পৃথক অধ্যায় বরাদ্দ করেছি। মৌলিক সংখ্যা হচ্ছে সেসব সংখ্যা যারা 1-এর চেয়ে বড় পূর্ণসংখ্যা এবং সেটি কেবল 1 এবং ওই সংখ্যাটি দ্বারাই নিঃশেষে বিভাজ্য হবে। খুবই সহজ-সরল জিনিস। এখন কোনো সংখ্যা মৌলিক কি না সেটি বের করার জন্য একটি প্রোগ্রাম লিখে ফেলা যাক।

 #include <stdio.h>   
 int is_prime(int n)   
 {   
     int i;   
     if (n < 2) {  
         return 0;  
     }  
     for(i = 2; i < n; i++) {   
         if(n % i == 0) {   
             return 0;   
         }   
     }   
     return 1;   
 }   

 int main()   
 {    
     int n;   
     while(1) {   
         printf("Please enter a number (enter 0 to exit): ");   
         scanf("%d", &n);   
         if(n == 0) {   
             break;   
         }    
         if(1 == is_prime(n)) {   
             printf("%d is a prime number.\n", n);   
         }   
        else {   
            printf("%d is not a prime number.\n", n);   
        }    
     }   
     return 0;   
 }  
 প্রোগ্রাম: ১০.১  

মৌলিক সংখ্যা নির্ণয়ের জন্য আমরা একটি ফাংশন লিখেছি যেটির প্যারামিটার হচ্ছে একটি ইন্টিজার নম্বর n। ফাংশনে আমরা nকে 2 থেকে n-1 পর্যন্ত সংখ্যাগুলো দিয়ে ভাগ করার চেষ্টা করেছি একটি লুপের সাহায্যে। যদি এর মধ্যে কোনো সংখ্যা দিয়ে n নিঃশেষে বিভাজ্য হয়, তবে আমরা সঙ্গে সঙ্গেই বলে দিতে পারি যে সেটি মৌলিক সংখ্যা নয় এবং ফাংশনটি 0 রিটার্ন করে। আর যদি সব সংখ্যা দিয়ে ভাগ করার পরও দেখা যায় যে কোন সংখ্যাই nকে নিঃশেষে ভাগ করতে পারেনি, তখন আমরা এই সিদ্ধান্তে আসতে পারি যে n একটি মৌলিক সংখ্যা। আর তখন ফাংশন থেকে 1 রিটার্ন করি। আমরা মৌলিক সংখ্যা নির্ণয় করা শিখে গেলাম! আমি প্রোগ্রামটি লিখার সময় যে পথ অবলম্বন করেছি সেটি হচ্ছে খুব সহজ-সরল পথ। প্রোগ্রামটিকে মোটেও ইফিশিয়েন্ট (efficient) বানানোর চেষ্টা করিনি। তোমরা খুব সহজেই ব্যাপারটি বুঝতে পারবে। প্রোগ্রামে ইনপুট হিসেবে 2147483647 দাও। এটি যে মৌলিক সংখ্যা সেটি বের করতে বেশ সময় লাগে। কারণ তখন 2147483647কে 2 থেকে 2147483646 পর্যন্ত সব সংখ্যা দিয়ে ভাগ করার ব্যর্থ চেষ্টা করা হয়। প্রোগ্রামটিকে আরও ইফিশিয়েন্ট করতে হবে।

একটি বুদ্ধি তোমাদের মাথায় এর মধ্যেই নিশ্চয়ই এসে গেছে। সেটি হচ্ছে 2 থেকে n-1 পর্যন্ত সব সংখ্যা দিয়ে ভাগ করার চেষ্টা না করে 2 থেকে n/2 পর্যন্ত সংখ্যাগুলো দিয়ে ভাগ করার চেষ্টা করলেই হয়। তাহলে প্রোগ্রামের গতি দ্বিগুণ হয়ে যাবে। এখন তোমরা আরেকটি বিষয় লক্ষ করো। কোন সংখ্যা যদি 2 দিয়ে নিঃশেষে বিভাজ্য না হয়, তবে সেটি অন্য কোন জোড় সংখ্যা দিয়ে নিঃশেষে বিভাজ্য হওয়ার প্রশ্নই আসে না। তাই 2 বাদে অন্য জোড় সংখ্যাগুলো (4, 6, 8, …) দিয়ে ভাগ করার চেষ্টা করাটা আসলে বোকামি। জোড় সংখ্যা দিয়ে বিভাজ্যতার পরীক্ষাটা আমরা ফাংশনের শুরুতেই করে নিতে পারি। এখন আমাদের ফাংশনটির চেহারা দাঁড়াবে এই রকম:

 int is_prime(int n)   
 {   
   int i;   
   if (n < 2) {  
     return 0;  
   }  
   if(n == 2) {   
     return 1;   
   }    
   if(n % 2 == 0) {   
     return 0;   
   }   
   for(i = 3; i <= n / 2; i = i + 2) {   
     if(n % i == 0) {   
       return 0;   
     }   
   }   
   return 1;   
 }  

প্রথমে আমরা পরীক্ষা করেছি n-এর মান 2 কি না। যদি 2 হয় তবে বলে দিয়েছি যে n মৌলিক সংখ্যা। তারপরে আমরা পরীক্ষা করেছি n জোড় সংখ্যা কি না। যদি জোড় হয়, তবে n মৌলিক সংখ্যা না, কেবল 2ই একমাত্র জোড় মৌলিক সংখ্যা যেটির পরীক্ষা আমরা একেবারে শুরুতেই করে ফেলেছি। তারপর আমরা 3 থেকে n / 2 পর্যন্ত সব বেজোড় সংখ্যা দিয়ে nকে ভাগ করার চেষ্টা করেছি। এখন তোমরা বিভিন্ন ইনপুট দিয়ে প্রোগ্রামটি পরীক্ষা করে দেখো। 2147483647 দিয়ে পরীক্ষা করলে বুঝতে পারবে যে প্রোগ্রামের গতি আগের চেয়ে বেড়েছে কিন্তু তার পরও একটু সময় লাগছে। আমার কম্পিউটারে চার সেকেন্ডের মতো সময় লাগছে। কিন্তু এত সময় তো দেওয়া যাবে না। তোমাদের যাদের গাণিতিক বুদ্ধিশুদ্ধি বেশি, তারা একটু চিন্তা করলেই প্রোগ্রামটির গতি বাড়ানোর একটি উপায় বের করে ফেলতে পারবে। সেটি হচ্ছে n-এর উৎপাদক বের করার জন্য আসলে n / 2 পর্যন্ত সব সংখ্যা দিয়ে পরীক্ষা করার দরকার নেই। n-এর বর্গমূল পর্যন্ত পরীক্ষা করলেই হয়। n = p x q হলে, p বা q যেকোনো একটি সংখ্যা অবশ্যই n-এর বর্গমূলের সমান বা তার ছোট হবে। বর্গমূল নির্ণয়ের জন্য আমরা math.h হেডার ফাইলের sqrt() ফাংশনটি ব্যবহার করব। আমাদের প্রোগ্রামটি দাঁড়াচ্ছে এই রকম:

 #include <stdio.h>   
 #include <math.h>   
 int is_prime(int n)   
 {   
     int i, root;  
     if(n == 2) {   
         return 1;   
     }     
     if(n % 2 == 0) {   
         return 0;   
     }   
     root = sqrt(n);   
     for(i = 3; i <= root; i = i + 2) {   
         if(n % i == 0) {   
             return 0;   
         }   
     }   
     return 1;   
 }   

 int main()   
 {    
     int n, m;   
     while(1) {   
         printf("Please enter a number (enter 0 to exit): ");   
         scanf("%d", &n);   
         if(n == 0) {   
             break;   
         }    
         if(1 == is_prime(n)) {   
             printf("%d is a prime number.\n", n);   
         }   
         else {   
             printf("%d is not a prime number.\n", n);   
         }   
     }   
     return 0;   
 }  
 প্রোগ্রাম: ১০.২  

এখন তোমরা প্রোগ্রামটি চালিয়ে বিভিন্ন ইনপুট দিয়ে পরীক্ষা করে দেখো। একটি কথা বলে দিই। প্রোগ্রামটায় একটি বাগ আছে (মানে ভুল আছে)। সেটি খুঁজে বের করে ঠিক করে ফেলো।

প্রাইম নম্বর বের করতে পেরে তোমরা নিশ্চয়ই বেশ খুশি? কিন্তু আমাদের চেষ্টা এখানেই থেমে থাকবে না। আমরা এখন দেখব আরেকটি চমৎকার পদ্ধতি, গ্রিক গণিতবিদ ইরাতোসথেনেস (Eratosthenes) আজ থেকে দুই হাজার বছরেরও আগে এই পদ্ধতি আবিষ্কার করেছিলেন। এজন্য-এর নাম হচ্ছে সিভ অব ইরাতোসথেনেস (Sieve of Eratosthenes)।

পদ্ধতিটি ব্যাখ্যা করা যাক। ধরো, আমরা 2 থেকে 40 পর্যন্ত সব মৌলিক সংখ্যা বের করব। শুরুতে সব সংখ্যা লিখে ফেলি: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 , 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40. এখন দেখো, তালিকার প্রথম সংখ্যা হচ্ছে 2। এবারে 2-এর সব গুণিতক (2 বাদে, মানে 2-এর চেয়ে বড়গুলো আরকী) বাদ দিয়ে দাও। তাহলে থাকবে: 2, 3, 5, 7, 9, 11, 13, 15, 17, 19 , 21, 23, 25, 27, 29, 31, 33, 35, 37, 39. এখন তালিকার দ্বিতীয় সংখ্যা 3-এর সব গুণিতক (3-এর চেয়ে বড়গুলো) বাদ দাও। 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37. এখন তালিকার তৃতীয় সংখ্যা 5-এর সব গুণিতক (5 বাদে) বাদ দাও। 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. পরবর্তী সংখ্যা হচ্ছে 7 কিন্তু সেটির গুণিতক খোঁজার চেষ্টা করা বৃথা। কারণ তালিকার সর্বোচ্চ সংখ্যা 37-এর বর্গমূল 7-এর চেয়ে ছোট। সুতরাং 7-এর যে গুণিতকগুলো তালিকায় ছিল সেগুলো ইতিমধ্যে তালিকা থেকে বাদ পড়েছে। কারণটি বুঝতে সমস্যা হচ্ছে? দেখো 7-এর গুণিতকগুলো ছিল 14, 21, 28, 35। 7-এর সঙ্গে যেসব সংখ্যা গুণ করে ওই গুণিতকগুলো পাওয়া যায় সেগুলো সবই 7-এর চেয়ে ছোট সংখ্যা এবং তাদের গুণিতকগুলো আমরা ইতিমধ্যেই বাদ দিয়ে দিয়েছি।

আরো পরিষ্কারভাবে বোঝার জন্য উইকিপিডিয়ার এই অ্যানেমেশনটি দেখতে পারো (এখানে 2 থেকে 120 পর্যন্ত সংখ্যাগুলোর মধ্যে মৌলিক সংখ্যাগুলো বের করা হয়েছে):

 
এবারে ইমপ্লিমেন্ট করার পালা। আমরা তালিকা রাখার জন্য একটি অ্যারে ব্যবহার করব। ধরা যাক, তার নাম হচ্ছে ara। অ্যারেটি এমনভাবে তৈরি করতে হবে, যাতে কোনো একটি সংখ্যা n-এর অবস্থা (অর্থাৎ সেটি মৌলিক কি না) ara[n] দিয়ে প্রকাশ করা যায়। যদি ara[n]-এর মান 1 হয়, তবে n মৌলিক সংখ্যা আর ara[n]-এর মান 0 হলে n মৌলিক সংখ্যা নয়। ইমপ্লিমেন্টেশনের আগে অ্যালগরিদমটা লেখা যাক:
ধাপ ১: ধরা যাক, অ্যারেতে nটি উপাদান আছে। শুরুতে অ্যারের সব উপাদানের মান 1 বসাই।
ধাপ ২: অ্যারের প্রতিটি উপাদানের জন্য সেটির মান 1 কি না তা পরীক্ষা করি। যদি 1, হয় তবে তৃতীয় ধাপে যাই।
ধাপ ৩: ওই সংখ্যাকে 2 থেকে m পর্যন্ত ক্রমিক সংখ্যাগুলো দিয়ে গুণ করি এবং গুণফল যত হবে, অ্যারের তত নম্বর উপাদানে শূন্য (0) বসাই। অর্থাৎ সেটি যে মৌলিক নয় তা চিহ্নিত করি। এখানে m-এর মান এমন হবে যেন ঐ সংখ্যার সঙ্গে m-এর গুণফল n-এর চেয়ে ছোট বা সমান হয়।

এখন তোমরা কোডটি লিখার চেষ্টা করো। কমপক্ষে তিন ঘণ্টা নিজে চেষ্টা করার পর এবারে আমার কোড দেখো।

 #include <stdio.h>   
 #include <math.h>   
 

 int size = 40;   
 int ara[40];   

 void print_ara()   
 {   
     int i;   
     for(i = 2; i < size; i++) {   
         printf("%4d", ara[i]);   
     }   
     printf("\n");   
     for(i = 2; i < size; i++) {   
         printf("----");   
     }   
     printf("\n");   
     for(i = 2; i < size; i++) {   
         printf("%4d", i);   
     }   
     printf("\n\n\n");    
 }   

 void sieve()   
 {   
     int i, j, root;   
     for(i = 2; i < size; i++) {   
         ara[i] = 1;   
     }   
     root = sqrt(size);   
     print_ara();   
     for(i = 2; i <= root; i++) {      
         if(ara[i] == 1) {   
             for(j = 2; i * j <= size; j++) {   
                 ara[i * j] = 0;          
             }   
             print_ara();   
         }   
     }   
 }   

 int is_prime(int n)   
 {   
     int i;   
     if(n < 2) {   
         return 0;   
     }   
     return ara[n];   
 }   

 int main()   
 {    
     int n, m;   
     sieve();   
     while(1) {   
         printf("Please enter a number (enter 0 to exit): ");   
         scanf("%d", &n);   
         if(n == 0) {   
             break;   
         }   
         if(n >= size) {   
             printf("The number should be less than %d\n", size);   
             continue;   
         }   
         if(1 == is_prime(n)) {   
             printf("%d is a prime number.\n", n);   
         }   
         else {   
             printf("%d is not a prime number.\n", n);   
         }   
     }      
     return 0;   
 }  
 প্রোগ্রাম: ১০.২  

প্রতিবার অ্যারের অবস্থা বোঝানোর জন্য আমি একটি ফাংশন ব্যবহার করেছি, print_ara()। তোমরা দেখো এবারে ইনপুট নেওয়ার আগেই আমরা sieve() ফাংশন কল করে অ্যারেটি তৈরি করে ফেলেছি। তারপর যতবারই ইনপুট নাও, কোনো চিন্তা নেই, ইনপুট যদি n হয় তবে ara[n]-এর মান পরীক্ষা করলেই চলে, মান যদি 1 হয় তবে n মৌলিক সংখ্যা, যদি 0 হয় তবে n মৌলিক সংখ্যা নয়। কত পর্যন্ত সংখ্যা হিসাব করতে চাও সেটি size-এ বসিয়ে দিলেই হবে। এখন এই প্রোগ্রামে গতি নিয়ে কোনো সমস্যা নেই। খুবই ফাস্ট (fast)। কিন্তু আর কোনো সমস্যা তোমাদের চোখে পড়ছে? তোমরা কি বুঝতে পারছ যে প্রোগ্রামটি অনেক বেশি মেমোরি খরচ করে? ধরো, আমরা যদি 100 কোটি পর্যন্ত সংখ্যা মৌলিক কি না সেটি বের করতে চাই, তাহলে তো আমাদের 100 কোটির একটি অ্যারে দরকার হবে। 'সময় বাঁচাব না মেমোরি' সমস্যায় প্রোগ্রামারদের প্রায়ই পড়তে হয়। আমাদের সমস্যার ক্ষেত্রে আমরা একটি মাঝামাঝি সমাধানে পৌঁছতে পারি। n-এর সর্বোচ্চ মান যত হবে তার বর্গমূলটিকে size-এর মান হিসেবে নিতে পারি। তোমাকে যদি বলা হয়, n-এর মান সর্বোচ্চ 100000000 (দশ কোটি) পর্যন্ত হতে পারে তাহলে তুমি এর বর্গমূল অর্থাৎ 10000 পর্যন্ত সংখ্যাগুলোর জন্য sieve ফাংশন ব্যবহার করে মৌলিক সংখ্যাগুলো বের করবে। তারপর কী করবে? নাহ্, আর কিছু বলা যাবে না, তোমরাই চিন্তা করে ঠিক করো কী করবে। আরেকটি কথা বলে দেওয়া দরকার। একটি ইন্টিজার কিন্তু চার বাইট জায়গা দখল করে, যেখানে একটি ক্যারেক্টার করে এক বাইট। সুতরাং ইন্টিজারের পরিবর্তে তোমরা ক্যারেক্টারের অ্যারে ব্যবহার করে মেমোরি খরচ চার ভাগের এক ভাগে নামিয়ে আনতে পারো। আমাদের তো আসলে ইন্টিজার অ্যারের দরকার নেই, কারণ অ্যারেতে কেবল দুই ধরনের মান থাকবে 0 বা 1। এটি ছাড়াও আমার লেখা sieve ফাংশনে আরও বেশ কিছু উপায় আছে ইফিসিয়েন্সি বাড়ানোর। এর মধ্যে একটি হচ্ছে গুণের বদলে যোগ করা। তোমরা সেটি করার চেষ্টা করো।