প্রাইম নিয়ে যত কথা – ১

নাম্বার থিওরির গুরুত্বপূর্ণ একটি টপিক হল প্রাইম নাম্বার বা মৌলিক সংখ্যা। আজ প্রাইম নাম্বার বা মৌলিক সংখ্যার উপর কিছু বেসিক আলোচনা করবো আমরা। আচ্ছা তাহলে আগে জানা যাক মৌলিক সংখ্যা কি? যেসব সংখ্যাকে ওই সংখ্যা এবং ১ ছাড়া আর কোন সংখ্যা দিয়ে ভাগ করা যায়না সেগুলোই মৌলিক সংখ্যা। যেমন ঃ ২ , ৩ , ৫ ইত্যাদি। আজ আমরা দেখবো কিভাবে সহজেই আমরা একটি সংখ্যা প্রাইম কিনা তা বের করার কোড। এরপর দেখবো কিভাবে একটি সংখ্যার প্রাইম ফ্যাক্টরাইজেশন করা যায়।

আমরা যেহেতু ইতিমধ্যে জেনে গেছি যে প্রাইম কিভাবে বুঝতে হয় তাহলে আমরা বলতে পারি যে কোন সংখ্যা N প্রাইম কিনা তা জানার জন্য ২ থেকে N-১ পর্যন্ত সংখ্যা দিয়ে ভাগ করে যদি দেখি যে N কে ভাগ করা যাচ্ছেনা তাহলেই ধরে নেব সংখ্যাটি প্রাইম।

তাহলে কোডে দেখি প্রসেসটা।

আমরা একটি বুলিয়ান ভ্যারিয়াবল এ প্রথমে true নিয়ে নিচ্ছি। যদি প্রাইম চেক করার সময় দেখি যে N কোন সংখ্যা দ্বারা বিভাজ্য তাহলে তা false করে দিব। তারপর এর মানের উপর নির্ভর করে বুঝবো প্রাইম নাকি প্রাইম না। খুবই সোজা কোড।

এখন আমাদের শুধু কোড করলেই হবেনা। কোড কি Efficient কিনা তাও দেখতে হবে। খেয়াল করে দেখি আমরা প্রাইম বাদে কোন সংখ্যাকে সর্বনিম্ন দুই ভাগে ভাগ করতে পারি। জোড় সংখ্যা গুলো কে। তার মানে আমরা যে সংখ্যাই নেই না কেন তার অর্ধেক থেকে বড় সংখ্যা ( < N) ওই সংখ্যা কে ভাগ করতে পারবেনা। যেমন ঃ ধরা যাক ১০। এর অর্ধেক হল ৫। আমরা খেয়াল করলেই দেখবো ৬ ৭ ৮ ৯ এগুলো ১০ এর ভাজক না। তাহলে আমরা কোড এ একটু পরিবর্তন আনি।

আমরা তাহলে আগের থেকে Efficient একটা কোড পেলাম। আচ্ছা এর থেকেও কি Efficient কোড করা যায়? এই প্রশ্নের উত্তর একটু পরে খুঁজি । তার আগে আরেকটা ব্যাপার দেখি আমরা।

১০০ = ১ * ১০০

     ২ * ৫০

     ৪ * ২৫

৫ * ২০

১০ * ১০

এখানে আমরা ১০০ এর Divisor গুলো বের করলাম। আমরা যদি জোড়া করি Divisor গুলোর তাহলে দেখবো ১ , ২ , ৪ , ৫ , ১০ এই সংখ্যাগুলো দিয়ে ১০০ কে ভাগ করলে আমরা ১০০ , ৫০ , ২৫ , ২০ , ১০ এগুলো পেয়ে যাচ্ছি। মজার ব্যাপার। তাহলে আমি সর্বনিম্ন কোন সংখ্যা পর্যন্ত চেক করলে সবগুলো Divisor পেয়ে যাচ্ছি ? ১০ পর্যন্ত। লক্ষ্য করলেই দেখবো যে ১০ ১০০ এর বর্গমূলের সমান। আমরা চাইলে অন্যান্য সংখ্যা দিয়েও চেক করে দেখতে পারি। প্রতিবারই আমরা দেখবো যে আমরা কোন সংখ্যার বর্গমূলের ভেতর চেক করলেই সবগুলো Divisor বের করতে পারব। তাহলে আমরা আমাদের আগের প্রশ্নের উত্তর পেয়ে গেলাম।আমরা কোন সংখ্যার Square Root পর্যন্ত লুপ চালালেই বের করতে পারবো সংখ্যাটি প্রাইম কিনা। এবার কোডে আসি।

যাক, এতক্ষণে আমরা অনেক Efficient একটা কোড পেলাম। এভাবেই তাহলে আমরা কোন সংখ্যা প্রাইম কিনা তা বের করতে পারবো।

এখন আমরা জানবো কিভাবে একটা সংখ্যার প্রাইম ফ্যাক্টর গুলো প্রিন্ট করতে হয়। একটি সংখ্যা নেই। ধরলাম ৩৬০। এর প্রাইম ফ্যাক্টরগুলো হল ২ ২ ২ ৩ ৩ ৫। অর্থাৎ এই প্রাইম গুলো গুন করলে আমরা ৩৬০ পাবো। এখন আমরা কিভাবে প্রিন্ট এর কাজ টা করব? আমরা আগের মতই সংখ্যার Square Root পর্যন্ত লুপ চালাবো আর Divisor পেলেই সেটাকে ওই সংখ্যা থেকে বাদ দিয়ে দিব। কোডে দেখি ব্যাপার টা।

কোড দেখে ঘাবড়ানোর কিছু নেই। ধীরে ধীরে আমরা দেখি কোডের প্রসেস। আমরা আমাদের প্ল্যান অনুযায়ী Square Root পর্যন্ত লুপ চালালাম। তারপর যদি কোন Divisor পাই তাহলে চেক এর ভেতরের While লুপ এর মাধ্যমে আমরা ওই সংখ্যা থেকে Divisor টা সম্পূর্ণভাবে বাদ দিয়ে দিচ্ছি আর প্রিন্ট করতেসি প্রতিবার। এখন এই কোড দেখে অনেক প্রশ্নই মনে জাগবে। আমরা যে Divisor বাদ দিচ্ছি তা যে Prime Divisor / Factor তার গ্যারান্টি কি? বা কোড এর শেষে আমরা যে অতিরিক্ত ( N > 1 ) এর চেক দিলাম তার দরকারই বা কি?

প্রথম প্রশ্নের উত্তরে আসি। যদি সংখ্যাটি জোড় হয় তাহলে তার Divisor গুলোর মাঝে ২ অবশ্যই থাকবে। আমরা যদি সবগুলো ২ কেই বাদ দিয়ে দেই তাহলে নতুন করে আর কোন জোড় Divisor পাওয়ার সম্ভাবনা রইলনা। বাকি রইল বিজোড় Divisor গুলো। যদি ৩ থাকে তাহলে ৩ বাদ দেয়ার সময় ৩ এর গুণিতক থাকলে এগুলোও বাদ পরে যাচ্ছে। তাই পরবর্তীতে লুপ এ আমরা ৩ এর কোন গুণিতক কে Divisor হিসেবে পাবোনা। তাহলে বোঝাই যাচ্ছে যে আমরা লুপ এর কন্ডিশন অনুযায়ী শুধু প্রাইম সংখ্যাগুলো কে Factor / Divisor হিসেবে পাচ্ছি।

এবার দ্বিতীয় প্রশ্ন এর উত্তর। আমরা কোড থেকে এটুকু অবশ্যই বুঝতে পারছি যে N কে ভাগ করার পর N ছোট হয়ে যাচ্ছে। তার ফলে আমাদের বাইরের লুপটার কন্ডিশন ও ছোট হচ্ছে। তাহলে এমন একটা পর্যায় আসবে যখন দুইটা প্রাইম গুন আকারে থাকবে। অথবা একটা প্রাইম থেকে যাবে। ধরি P1 আর P2 দুইটা প্রাইম সংখ্যা (P1 <= P2)। এখন এদের গুনফলের Square root যদি আমরা বের করি তাহলে (P1 <= Square root(P1,P2) <= P2) হবে। লুপের কন্ডিশন অনুযায়ী P1 আমরা বাদ দিয়ে দিব। এখন P2 এর কি হবে ? এর Square root তো এর থেকে ছোট। তাই এইটা চেক হওয়ার আগেই লুপ Terminate হয়ে যাচ্ছে। তাই আমরা অতিরিক্ত একটি চেক দিলাম যে N ১ এর চেয়ে বড় থাকলে সেটাও আমরা প্রিন্ট করে দিব।

আজ তাহলে এ পর্যন্তই। এর পরের টিউটোরিয়াল এ আমরা দেখবো কিভাবে ১০^৭ পর্যন্ত প্রাইম সংখ্যা সহজেই বের করা যায়।