ইংরেজিতে এই পদ্ধতিকে বলা হয় 'Sieve of Eratosthenes', বাংলায় ইরাটোস্থেনিসের ছাঁকনি। এই ছাঁকনির কাজ কী? এই ছাঁকনি অনেকগুলো সংখ্যা থেকে মৌলিক সংখ্যাগুলো বেছে আলাদা করে।
মৌলিক সংখ্যা হলো সেসকল সংখ্যা, যাদের ১ এবং ঐ সংখ্যা ছাড়া আর কোনো সংখ্যা দিয়েই ভাগ করা যায় না। কোনো সংখ্যা মৌলিক কি না জানা খুব সহজ, সবগুলো উৎপাদক বের করে দেখবো মৌলিক কি না। আচ্ছা, সংখ্যাটা যদি অনেক বড় হয়, যেমন, ১৯৩৩ মৌলিক কি না বের করার জন্য তো ১৯৩২টি সংখ্যা দিয়ে ভাগ করে দেখতে হবে! এরও সহজ বুদ্ধি আছে, কোনো সংখ্যা মৌলিক কি না, সেটা জানতে সবগুলো সংখ্যা দিয়ে ভাগ করার দরকার নেই, কেবল ঐ সংখ্যার বর্গমূল পর্যন্ত দেখলেই হবে। কেন?
মনে করুন, N একটা সংখ্যা এবং N = a×b। এখন আমাদের প্রমাণ করতে হবে a, b এর মধ্যে একটা অবশ্যই N এর বর্গমূলের চেয়ে ছোট, আরেকটা N এর বর্গমূলের চেয়ে বড়। শুরুতে ধরে নিই, দুটিই N এর বর্গমূলের চেয়ে বড়। তাহলে কিন্তু a, b গুণ করলে N এর চেয়ে বড় হয়ে যাবে। এজন্য কোনো সংখ্যা যদি মৌলিক না হয়, অবশ্যই তার একটা না একটা উৎপাদক থাকবে, যা N এর বর্গমূলের চেয়ে ছোট। এখান থেকে সহজেই বোঝা যায়, আরেকটি উৎপাদক হবে N এর বর্গমূলের চেয়ে বড়।
আমরা মৌলিক সংখ্যা বের করার একটা পদ্ধতি পেলাম এবং এটা মোটামুটি ভাল একটা পদ্ধতি। কিন্তু আমাদের যদি অনেকগুলো সংখ্যা থেকে মৌলিক আর অমৌলিক সংখ্যাগুলো আলাদা করতে বলা হয়, তখন কিন্তু প্রতিটা সংখ্যার জন্য আলাদা আলাদা করে উৎপাদক বের করে দেখাটা মোটেও ভাল কোনো পদ্ধতি না। এজন্যই দরকার পড়ে ইরাটোস্থেনিসের ছাঁকনি। এই পদ্ধতি এখনও বড় বড় রেঞ্জের মধ্যে মৌলিক সংখ্যা বের করতে এক কার্যকর অ্যালগরিদম, কম্পিউটার জগতে এর রয়েছে বিপুল ব্যবহার।
খুব সাধারণভাবে চিন্তা করা যাক। যে সংখ্যা কোনো একটা মৌলিক সংখ্যার গুণিতক, নিঃসন্দেহে সেটি আর মৌলিক নয়। এই বিষয়টি কাজে লাগানো যাক। মনে করি, ১-২০ এর মধ্যে সব মৌলিক সংখ্যা বের করতে চাই। শুরুতে আমাদের তালিকায় সব সংখ্যাই থাকবে, আস্তে আস্তে অমৌলিক সংখ্যাগুলো ছাঁকনি বেয়ে পড়ে যাবে, রয়ে যাবে মৌলিক সংখ্যাগুলো। এটা কীভাবে হবে?
আমরা শুরু করবো ২ থেকে। তালিকা থেকে ২ এর সব গুণিতক বাদ দিয়ে দিই (৪, ৬, ৮, ১০, ১২, ১৪, ১৬, ১৮, ২০)। এরপর আসা যাক, ৩ এর উৎপাদকে। তিনের প্রথম উৎপাদক হলো ৬, কিন্তু এটি আগেই বাদ পরে গেছে, ২ এর গুণিতক হওয়ায়। তাহলে আমরা শুরু করলাম ৩ এর বর্গ ৯ থেকে (৯, ১৫)। এবার পরের সংখ্যা হওয়া উচিত ৪, কিন্তু এটি আগেই তালিকা থেকে বাদ পড়েছে। পরের সংখ্যা ৫, কিন্তু এর সকল গুণিতকই বাদ পড়ে গেছে। তাহলে আমাদের হাতে রইলো কী? ২, ৩, ৫, ৭, ১১, ১৩, ১৭, ১৯; মানে ১-২০ এর মধ্যে সকল মৌলিক সংখ্যা।
কীভাবে বুঝলাম ৫ আসলেই আমাদের থেমে যেতে হবে? আসলে আমাদের থামার কথা ৪ এ। কারণ ২০ এর বর্গমূল করলে ৪.৪৭। তার মানে ২০ এর মধ্যে এমন কোন সংখ্যা নেই যাদের এমন এক জোড়া উৎপাদক আছে, যার দুটিই ৪ এর চেয়ে বড়।
বুঝতে একটু অসুবিধা হলে নিচের অ্যানিমেশনটি দেখা যাক। এটি ১-১০০ পর্যন্ত সব মৌলিক সংখ্যা বের করে। শুরুতে ২ এর সব গুণিতক বাদ দিয়ে দেব, তারপর ৩… এরকম চলতে থাকবে। সবশেষে যেগুলো পড়ে থাকবে, সেগুলোই মৌলিক সংখ্যা।
ইরাটোস্থেনিসের ছাঁকনি থেকে আরেকটা গুরুত্বপূর্ণ সিদ্ধান্ত নেয়া যায়। সেটা হলো- ১ কোনো মৌলিক সংখ্যা নয়, কারণ ১-কে মৌলিক হিসেবে ধরলে ১ এর সব গুণিতক বাদ পড়ে যাবে, মানে পৃথিবীতে আর কোনো মৌলিক সংখ্যাই থাকবে না! এখানে আরেকট বিষয় উল্লেখ্য, ১ কিন্তু কম্পোজিট সংখ্যাও না। একে বলা হয় একক সংখ্যা।
ইরাটোস্থেনিসের সীভের ধারণা ব্যবহার করে আরও অনেক মৌলিক সংখ্যা নির্ণয়ের উচ্চতর অ্যালগরিদম এসেছে। একদম বেসিক সীভ ইমপ্লেমেন্টেশন করে ১০ মিলিয়ন পর্যন্ত সব মৌলিক সংখ্যা বের করার সি প্লাস প্লাস কোড এখানে দেওয়া হলো, সাধারণ মানের কম্পিউটারে এই কাজটি করতে মোটামুটি ১ সেকেন্ডেরও কম সময় লাগে।
Comments
Post a Comment