প্রাইম বা মৌলিক সংখ্যা আমরা সবাই চিনি। কম্পিউটার বিজ্ঞানে মৌলিক সংখ্যার গুরুত্ব অনেক।
বিভিন্ন গুরুত্বপূর্ণ কাজে আমাদের মৌলিক সংখ্যার দরকার হয়। কাজেই একটি সংখ্যা মৌলিক কি না, একটি সীমার মাঝে সব মৌলিক সংখ্যাকে বের করা বা একটি সংখ্যার সব মৌলিক উৎপাদক বের করা এরূপ বিভিন্ন কাজ আমাদের অহরহ করতে হয়। এ পর্বে আমরা এই সমস্যাগুলো সমাধানের অ্যালগরিদম দেখব।
মৌলিক সংখ্যা
মৌলিক বা প্রাইম সংখ্যা বলতে আমরা বুঝি এমন সব সংখ্যা যাদের কোনো উৎপাদক নেই। অর্থাৎ অন্য কোনো সংখ্যা দিয়ে আমরা মৌলিক সংখ্যাকে ভাগ করতে পারব না। কথাটি আসলে আংশিক সত্যি। কারণ ১ দিয়ে সব সংখ্যাকে ভাগ করাই যায়। বা যেকোনো সংখ্যাকে ওই সংখ্যা দ্বারা তো ভাগ করা যায়। কাজেই আমাদের সংজ্ঞায় এই কথাটি যোগ করে দিতে হবে। যদি ১ এবং ওই সংখ্যা বাদে অন্য কোনো সংখ্যা দ্বারা ভাগ না করা যায় তাহলেই একটি সংখ্যাকে আমরা মৌলিক সংখ্যা বলতে পারব। তবে মনে রাখতে হবে, সংখ্যাগুলোকে অবশ্যই পূর্ণ সংখ্যা হতে হবে। যদিও ১ সংখ্যাটির ক্ষেত্রেও এই শর্ত খাটে, তবে অধিকাংশ গণিতবিদ ১ কে মৌলিক সংখ্যা স্বীকৃতি দিতে রাজি নন। কাজেই প্রথম মৌলিক সংখ্যা হলো ২। এর পরেরগুলো হলো ৩, ৫, ৭, ১১, ১৩, ১৭, ১৯, ২৩ ইত্যাদি। আরও অনেক সংখ্যাই আছে মৌলিক। দেখি তো তুমি কত দূর পর্যন্ত বের করতে পারো?
সংখ্যার মৌলিকত্ব নির্ণয়
মৌলিক সংখ্যা নাহয় আমরা বুঝলাম। কিন্তু একটা সংখ্যা মৌলিক কি না তা আমরা কীভাবে বুঝব? আসলে একটি সংখ্যা মৌলিক কি না তা বোঝার জন্য আমাদের হাতে একটিই উপায় রয়েছে, তা হলো বিভিন্ন সংখ্যা দিয়ে সংখ্যাটিকে ভাগ করে দেখার চেষ্টা করা। যদি যেকোনো একটি সংখ্যা দিয়ে ভাগ করা যায়, তাহলে আমরা সঙ্গে সঙ্গে বলে দিতে পারব যে সংখ্যাটি মৌলিক না। কিন্তু মৌলিক কি না কীভাবে বলব? এই ভাগ করার কাজ শেষই বা হবে কবে?
আমরা যুক্তি থেকে এই ব্যাপারে কিছু সিদ্ধান্তে আসতে পারি। ধরি যে সংখ্যাটির মৌলিকত্ব আমরা নির্ণয় করতে চাচ্ছি তার মান N।
N থেকে বড় সংখ্যা দিয়ে ভাগ করে দেখার চেষ্টা বৃথা। কারণ কোনো সংখ্যাকেই তার চেয়ে বড় সংখ্যা দিয়ে ভাগ করা যায় না।
১ দিয়ে ভাগ করব না।
N দিয়ে ভাগ করব না।
তাহলে আমরা দেখতে পাচ্ছি, ভাগ করে দেখার মতো সংখ্যা বাকি থাকছে ২ থেকে N-১। যেমন N এর মান যদি হয় ৫ তাহলে আমরা ২, ৩, ৪ দিয়ে ভাগ করে দেখব। যেহেতু এর কোনোটি দিয়েই ৫ কে ভাগ করা যায় না। কাজেই ৫ একটি মৌলিক সংখ্যা। ধরো N এর মান ৫১। তাহলে আমাদের ২, ৩, ৪, ৫০ ইত্যাদি সংখ্যা দিয়ে ভাগ করে দেখতে হবে। যেহেতু ৩ দিয়ে ৫১ কে ভাগ করা যায়, কাজেই ৫১ একটি অমৌলিক সংখ্যা, যাকে আমরা কম্পোজিট সংখ্যাও বলে থাকি।
এই উপায়টির প্রোগ্রামটি (সি ভাষায় লেখা) নিচের চিত্রে দেখানো হলো।
সমস্যা হলো এই উপায়ে বড় বড় সংখ্যার মৌলিকত্ব বের করব কীভাবে? এত এত সংখ্যা দিয়ে ভাগ করে দেখা তো খুব কঠিন। এ জন্য আমরা দুটি উপায় দেখব, যে উপায়গুলোর মাধ্যমে আমরা আরও কম পরিশ্রমের মাধ্যমে বের করতে পারি একটি সংখ্যা মৌলিক কি না।
সমস্যা হলো এই উপায়ে বড় বড় সংখ্যার মৌলিকত্ব বের করব কীভাবে? এত এত সংখ্যা দিয়ে ভাগ করে দেখা তো খুব কঠিন। এ জন্য আমরা দুটি উপায় দেখব, যে উপায়গুলোর মাধ্যমে আমরা আরও কম পরিশ্রমের মাধ্যমে বের করতে পারি একটি সংখ্যা মৌলিক কি না।
মৌলিকত্ব নির্ণয়ের পদ্ধতি ১
ভাগ করে দেখা ছাড়া আমাদের হাতে আসলে অন্য কোনো উপায় নেই। কিন্তু একটু বুদ্ধি খাটালে আমাদের যে কয়টি সংখ্যা দিয়ে ভাগ করে দেখতে হবে তা কমানো সম্ভব। আসলে গাণিতিকভাবে প্রমাণ করা সম্ভব যে আসলে একটি সংখ্যার মৌলিকত্ব নির্ণয় করার জন্য ওই সংখ্যাটির বর্গমূল বা তার ছোট সংখ্যাগুলো দিয়ে ভাগ করে দেখাই যথেষ্ট। উদাহরণস্বরূপ আমরা বলতে পারি, ১২৭ সংখ্যাটি মৌলিক কি না বোঝার জন্য আগের নিয়মে আমরা ২ থেকে ১২৬ পর্যন্ত সংখ্যা দিয়ে ১২৭ কে ভাগ করে দেখার চেষ্টা করতাম। কিন্তু আমাদের এখনকার পদ্ধতি বলে, এটার দরকার নেই। ১২৭-এর বর্গমূল হচ্ছে ১১ (দশমিকের পরের অংশকে বিবেচনায় না নিয়ে)। কাজেই ১২৭ মৌলিক কি না পরীক্ষা করার জন্য আমাদের ২ থেকে ১১ পর্যন্ত সংখ্যাগুলো দিয়ে ভাগ করে দেখলেই চলবে। যেহেতু ২ থেকে ১১ পর্যন্ত কোনো সংখ্যা দ্বারাই ১২৭ কে ভাগ করা যায় না, কাজেই ১২৭ একটি মৌলিক সংখ্যা। এই পদ্ধতির প্রোগ্রামটি নিচে দেওয়া হলো।
কিন্তু এই নিয়মের প্রমাণ কী? প্রমাণটি করার জন্য আমরা নিয়মটিকে অন্যভাবে বলতে পারি, ‘যদি কোনো সংখ্যা অমৌলিক হয়, তাহলে তার অন্তত একটি উৎপাদক থাকবে, যা ওই সংখ্যার বর্গমূল থেকে ছোট বা সমান।’ এখন যদি আমরা ধরে নিই যে অমৌলিক সংখ্যার ক্ষেত্রে এমন হওয়া সম্ভব যে তার সবগুলো উৎপাদকই বর্গমূল থেকে বড়। আমরা জানি, যেকোনো সংখ্যার উৎপাদকগুলো জোড়ায় জোড়ায় আসে। যেমন ৩৬ সংখ্যার উৎপাদকগুলো হলো: 1 x 36, 2 x 18, 3 x 12, 4 x 9 এবং 6 x 6। তাহলে এ রকম এক জোড়া উৎপাদক যদি আমরা নিই এবং দাবি করি যে দুটি উৎপাদকই বর্গমূল থেকে বড়, তাহলে তাদের গুণ করলে তো মূল সংখ্যাটি থেকে বড় কোনো সংখ্যা পাওয়া যাবে, মূল সংখ্যাটি পাওয়া যাবে না। কাজেই নিশ্চয়ই আমাদের যে দাবি ছিল সব উৎপাদকই বর্গমূল থেকে বড় হবে, সে দাবিতে ভুল আছে। সুতরাং প্রুফ বাই কন্ট্রাডিকশনের মাধ্যমে আমরা বলতে পারি যে প্রত্যেক অমৌলিক সংখ্যারই তার বর্গমূল থেকে ছোট বা সমান এক বা একাধিক উৎপাদক আছে।
মৌলিকত্ব নির্ণয়ের পদ্ধতি ২
আমরা আরেকটু মাথা খাটালে বের করতে পারি যে যখন বিভিন্ন সংখ্যা দিয়ে ভাগ করে দেখছি, তখন শুধু মৌলিক সংখ্যাগুলো দিয়ে ভাগ করলেই যথেষ্ট। অমৌলিক সংখ্যাগুলো দিয়ে ভাগ করার চেষ্টা করার দরকার নেই। তার মানে আগের উদাহরণে ১২৭ মৌলিক কি না বের করার জন্য আমরা শুধু ২, ৩, ৫, ৭ এবং ১১ দিয়ে ভাগ করে দেখলেই বলে দিতে পারি যে ১২৭ একটি মৌলিক সংখ্যা। কিন্তু একটি সীমার মধ্যে সব মৌলিক সংখ্যাকে পাব কীভাবে? সেটির জন্য আমাদের একটি চমৎকার উপায় রয়েছে।
এরাটসথিনিসের ছাঁকনি
এরাটসথিনিস ছিলেন একজন গ্রিক গণিতবিদ। একটি সীমার মধ্যে কোন কোন সংখ্যা প্রাইম, সেটি বের করার জন্য তিনি চমৎকার একটি পদ্ধতি বের করেছিলেন, যার নাম হলো সিভ অব এরাটসথিনিস বা এরাটসথিনিসের ছাঁকনি। এই পদ্ধতি কাজ করে নিচের উপায়ে:
সংখ্যাগুলোকে পাশাপাশি লেখা হবে।
প্রথমে ২ থেকে বড় যেসব সংখ্যা ২ দ্বারা বিভাজ্য সে সংখ্যাগুলোকে কেটে দেওয়া হবে।
এরপর প্রথম যে সংখ্যা এখনো কাটা যায়নি (যেমন ৩) ওই সংখ্যাটি থেকে বড় যেসব সংখ্যা ওই সংখ্যা দ্বারা বিভাজ্য তাদের সবাইকে কেটে দেওয়া হবে।
এরপর আবার পরের সংখ্যাটি নেওয়া হবে, যেটি এখনো কাটা যায়নি এবং আগের কাজটি আবারও করা হবে।
এ রকমভাবে চলতে থাকবে যতক্ষণ পর্যন্ত সব সংখ্যা নিয়ে কাজ করা শেষ না হয়।
যেসব সংখ্যা কাটা যায়নি, সেগুলো মৌলিক সংখ্যা। যেমন উদাহরণস্বরূপ, যদি আমরা ১ থেকে ২০ পর্যন্ত সংখ্যার জন্য উপরিউক্ত পদ্ধতি চালাই:
২, ৩, ৪, ৫, ৬, ৭, ৮, ৯, ১০, ১১, ১২, ১৩, ১৪, ১৫, ১৬, ১৭, ১৮, ১৯, ২০। ১ বাদ কারণ, ১ মৌলিক সংখ্যা নয়।
শুরুতে ২ দিয়ে কাটা হবে। ২, ৩,
৪, ৫,৬, ৭,৮, ৯,১০, ১১,১২, ১৩,১৪, ১৫,১৬, ১৭,১৮, ১৯,২০।এরপর দেখতে পাচ্ছি ৩ কাটা যায়নি, কাজেই এরপর ৩ দিয়ে কাটা যাবে। ২, ৩,
৪, ৫,৬, ৭,৮,৯,১০, ১১,১২, ১৩,১৪,১৫,১৬, ১৭,১৮, ১৯,২০।এরপর ৫। ২, ৩,
৪, ৫,৬, ৭,৮,৯,১০, ১১,১২, ১৩,১৪,১৫,১৬, ১৭,১৮, ১৯,২০।এভাবে করে চালাতে থাকলে শেষ পর্যন্ত পাব ২, ৩,
৪, ৫,৬, ৭,৮,৯,১০, ১১,১২, ১৩,১৪,১৫,১৬, ১৭,১৮, ১৯,২০। কাজেই এখানে যেসব সংখ্যা কাটা পড়েনি তারাই মৌলিক সংখ্যা। এরা হলো ২, ৩, ৫, ৭, ১১, ১৩, ১৭ এবং ১৯।