ডিভিজর এবং প্রাইম নাম্বার(Divisor & Prime number)

 

ধরি, n এবং d দুইটি পূর্ণ সংখ্যা। d হচ্ছে n এর সমান বা ছোট এমন একটি সংখ্যা যা n কে ভাগ করতে পারে কোন ভাগশেষ না রেখেই। যেমন, n = 15 এবং d = 5 হয় তাহলে n কে d দিয়ে ভাগ করলে ভাগফল হবে 3 এবং ভাগশেষ হবে 0। তাই এখানে d হচ্ছে n এর ডিভিজর। n নিজেও n এর একটি ডিভিজর।

তাহলে এখন জানি ডিভিজর কাকে বলে। কিন্তু, একটি সংখ্যার ডিভিজর গুলো বের করব কীভাবে? বা, একটি সংখ্যার কয়টি ডিভিজর আছে? কাজটি কিন্তু খুব সহজ, শুধু 1 থেকে n পর্যন্ত লুপ চালিয়ে দেখব কোন কোন সংখ্যা দিয়ে n কে ভাগ করা যায়। 

void find_divisor(int n) {   for (int i = 1;i <= n;i++) {     if (n%i == 0) {       // if i divide n       cout << i << ' ';     }   }   cout << '\n'; }

কিছু সংখ্যা দিয়ে টেস্ট করলে দেখা যাবে n নিজে ছাড়া সবথেকে বড় ডিভিজর n/2 এর থেকে বড় নয়। তাহলে আমরা যেহেতু জানি n নিজেও সবসময় একটি ডিভিজর তাই এই একটি নাম্বার পরীক্ষা করার জন্য n/2 থেকে n পর্যন্ত সংখ্যা গুলো অযথা পরীক্ষা করার দরকার নেই। তাহলে n/2 পর্যন্ত লুপ চালিয়েই দেখতে পারি। এতে কাজ অর্ধেক কমে গেল।

void find_divisor(int n) {   for (int i = 1;i <= n/2;i++) {     if (n%i == 0) {       // if i divide n       cout << i << ' ';     }   }   cout << '\n'; }

প্রথমে দেখেছিলাম, n = 15 এবং d = 5 হয় তাহলে n কে d দিয়ে ভাগ করলে ভাগফল হয় 3। এখানে 3 নিজেও কিন্তু n এর একটি ডিভিজর। তাহলে আমরা n এর একটি ডিভিজর পেলে বাকি অন্যটিও পেয়ে যাচ্ছি। কারণ, n কে অবশ্যই দুইটি সংখ্যার গুণফল হতে হবে (n = a * b)। n = 12 এর জন্য আমরা কিছু ডিভিজর দেখতে পারি। 

12 = 1 * 12
12 = 2 * 6
12 = 3 * 4

এখানে একটি বিষয় লক্ষণীয় যে, n বর্গমূল বা স্কয়ার রুট হচ্ছে 3(যেহেতু n একটি পূর্ণ সংখ্যা) এবং অর্ধেক ডিভিজর গুলো সবসময় n এর বর্গমূল থেকে ছোট বা সমান থাকবে এবং বাকিগুলো n এর বর্গমূল থেকে বড় থাকবে। তাহলে আমরা এখন n এর ডিভিজর গুলো বের করার জন্য 1 থেকে n এর স্কয়ার রুট পর্যন্ত লুপ চালিয়েই বের করে ফেলতে পারি। কিন্তু এখানে আমাদের একটি বিষয় খেয়াল রাখতে হবে। তা হচ্ছে, n পূর্ণবর্গ সংখ্যা কিনা। n পূর্ণবর্গ সংখ্যা হলে একটি ডিভিজর হয়ত দুইবার কাউন্ট করে ফেলব। 3 * 3 = 9 এখানে ভাজক ও ভাগফল কিন্তু আলাদা নয়(ভাজক = divisor এবং ভাগফল = quotient)। তাহলে এটিও বলা যায় n এর ডিভিজর সংখ্যা সবসময় জোর হবে শুধু n যদি পূর্ণবর্গ সংখ্যা না হয়। যেমন, যদি n = 16 হয়।

16 = 1 * 16
16 = 2 * 8
16 = 4 * 4

নিচে তাহলে একটি ফাংশন দেখি যেটি 1 থেকে n এর বর্গমূল পর্যন্ত লুপ চালিয়ে n এর সবগুলো ডিভিজর বের করে ফেলবে। 

void find_divisor(int n) {   // sqrt() function return square root of n   int sqrt_n = sqrt(n);   for (int i = 1;i <= sqrt_n;i++) {     if (n%i == 0) {       cout << i << ' ';       if (n/i != i){         // if divisor & quotient are not same         cout << n/i << ' ';       }     }   }   cout << '\n'; }

"ডিভিজর" নাম্বার থিওরি ও কম্পেটিটিভ প্রোগ্রামিং এর খুবই গুরুত্বপূর্ণ একটি টপিক। তাই কোনরকম অস্পষ্টতা রাখা চলবে না।

এবার আলোচনা করা যাক প্রাইম নাম্বার নিয়ে। প্রথমেই প্রশ্ন আসে প্রাইম নাম্বার কী? যদিও ডিভিজর ও প্রাইম নাম্বার এই বিষয়গুলো ছোটবেলার পড়া, তারপরেও আমার মত যারা ফাঁকি দিয়ে এসেছে :| তাদের কথা ভেবে চেষ্টা করতেছি একটু বিস্তারিত আলোচনা করতে। ত সহজ কথায় "প্রাইম নাম্বার হচ্ছে সেই সংখ্যা যার দুইটির বেশি ডিভিজর নেই"। মানে 1 এবং নিজেকে বাদ দিলে আর কোন ডিভিজর নেই ঐ সংখ্যার। যেমন, 2, 3, 5, 7 ইত্যাদি। বাকি সংখ্যা গুলোকে বলা হয় কম্পোজিট নাম্বার। এক্ষেত্রে শুধু 1 একটু আলাদা কারণ এটি আসলে প্রাইমের সংজ্ঞাতেও পড়েনা আবার কম্পোজিটের সংজ্ঞাতেও পড়েনা। তবে কোন কোন প্রবলেমে আবার 1 কে প্রাইম হিসেবে ধরে নেওয়া হয়। সেক্ষেত্রে মন দিয়ে প্রবলেম পড়ার কোন বিকল্প নেই। 2 হচ্ছে একমাত্র জোর সংখ্যা যেটি প্রাইম, বাকিসব প্রাইম নাম্বারই বিজোর।

তাহলে একটি সংখ্যা প্রাইম নাকি কম্পোজিট? এটি বের করা কিন্তু খুব সোজা। অবশ্যই কোড দেখার আগে একবার চেষ্টা করে দেখবেন। একটি সংখ্যা প্রাইম নাকি কম্পোজিট এটি দেখার জন্য আগের মতই n এর স্কয়ার রুট পর্যন্ত লুপ চালিয়ে দেখব এর মাঝে কোন একটি সংখ্যা n কে ভাগ করতে পারে কিনা। যদি একটি সংখ্যাও ভাগ করতে পারে তবে অবশ্যই সংখ্যাটি প্রাইম নয়। তবে শুরু কিন্তু 1 থেকে করা যাবে না কারণ, প্রাইম নাম্বারের সংজ্ঞা অনুযায়ী 1 প্রাইম নাম্বারকেও ভাগ করতে পারে।

bool isprime(int n) {   if (n < 2)return false;   int sqrtn = sqrt(n);   // sqrt() function return square root of n   for (int i = 2;i <= sqrtn;i++) {     if (n%i == 0) {       // if n is divide by i then n has more than two divisors       return false;     }   }   // if all conditions in the above are false then n is prime   return true; }

আচ্ছা, 2 ছাড়া সব জোড় সংখ্যাই কম্পোজিট। তাহলে n যদি 2 এর থেকে বড় কোন জোর সংখ্যা হয় তবে জোর নাম্বার গুলো দিয়ে পরীক্ষা করার দরকার নেই। লুপ শুরুর আগেই বলে দিতে পারি এটি প্রাইম নয়। আর লুপে গিয়ে 3 থেকে শুরু করে শুধু বিজোর সংখ্যা গুলো দিয়ে এখন পরীক্ষা করব। এতে কিন্তু n এর স্কয়ার রুটের ও অর্ধেক কাজ কমে যাচ্ছে। এটির কোড আর দিয়ে দিলাম না।

ডিভিজর ও প্রাইম নাম্বার দুটোই সমান গুরুত্বপূর্ণ টপিক। অস্পষ্টতা থাকলে আবার পড়ুন এরপরেও কোনকিছু বুঝতে সমস্যা হলে কমেন্ট করতে পারেন।

এই বিষয়ে আরো টিউটোরিয়াল।
টিউটোরিয়াল ১

প্র্যাক্টিস প্রবলেমঃ
Divisors 
Is Prime