সংখ্যাতত্ত্ব: সিভ দিয়ে হোক শুরু

আজ থেকে প্রায় দুই হাজার তিন শ বছর আগে প্রখ্যাত গ্রিক গণিতবিদ ইউক্লিড প্রমাণ করে গেছেন, প্রাইম বা মৌলিক সংখ্যার কোনো শেষ নেই। সেই থেকে চলছে মানুষের মৌলিক সংখ্যা বের করার সাধনা। সর্বকালের অন্যতম শ্রেষ্ঠ গণিতবিদ কার্ল ফ্রিডরিখ গাউস ১৮৪৯ সালে ৩০ লাখ পূর্ণ সংখ্যার ভেতরের মৌলিক সংখ্যার প্রায় সবগুলো গুনে ফেলেছিলেন নিজে থেকেই। কম্পিউটারের এ যুগে বড় বড় মৌলিক সংখ্যা আমরা চোখের নিমেষেই বের করতে পারি। তবে সে জন্য আমাদের জানতে হবে, প্রোগ্রামিং আর দুই হাজার বছরের পুরোনো একটি অ্যালগোরিদম। এই টিউটোরিয়ালের শেষে আশা করি, তোমরাও গাউসের সমস্যাটির সঠিক সমাধান নিজেরাই বের করতে পারবে।

মৌলিক সংখ্যা কী?
প্রাইম বা মৌলিক সংখ্যা হচ্ছে এমন একটি ধনাত্মক পূর্ণ সংখ্যা, যাকে কেবল ১ ও ওই সংখ্যাটি দিয়েই ভাগ করা যায়। যেমন ৭ কে কেবল ১ আর ৭ দিয়েই ভাগ করা যায়। কিন্ত ৬ মৌলিক সংখ্যা নয়, কারণ ২ আর ৩ দিয়েও ৬ কে ভাগ করা যায়। উল্লেখ্য, ১ কিন্তু মৌলিক সংখ্যা নয়। এখন যদি তোমাকে একটি সংখ্যা দিয়ে জিজ্ঞেস করা হয়, সংখ্যাটি মৌলিক কি না, তাহলে তুমি চাইলেই হাতেকলমে কাজটি করে ফেলতে পারবে। তোমাকে যদি ২৫ সংখ্যাটি দেওয়া হয়, তাহলে তুমি নিচের মতো করে চেষ্টা করে দেখো:

প্রথমে ২৫ কে ২ দিয়ে ভাগ করে দেখা গেল ভাগশেষ ১, সুতরাং এখনো ২৫ মৌলিক হতে পারে।
তারপর ২৫ কে ৩ দিয়ে ভাগ করে দেখা গেল ভাগশেষ তাও ১, সুতরাং সামনে এগোনো উচিত।
এবার ২৫ কে ৪ দিয়ে ভাগ করে দেখা গেল ভাগশেষ আবারও ১, বিধিবাম।
কিন্ত ২৫ কে ৫ দিয়ে নিঃশেষে ভাগ করা গেল! তাহলে, ২৫ অন্তত আর যাই হোক, মৌলিক সংখ্যা নয়।

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

প্রাইম টেস্ট করার সিপ্লাসপ্লাস কোড: https://go.toph.co/32iVqS8
এখন চল তাড়াতাড়ি আমরা এই সমস্যাটা সমাধান করে ফেলি: https://go.toph.co/is-prime-bn

এখন একটা সমস্যা আছে এই প্রক্রিয়ায়। ধর, ৭১ সংখ্যাটি মৌলিক কি না, এটা তুমি বের করতে চাইছ। তাহলে ওপরের পদ্ধতি অবলম্বন করলে তোমাকে ৬৯টা সংখ্যা দিয়ে ভাগ করে করে শেষ পর্যন্ত সিদ্ধান্তে আসতে হবে যে ৭১ সংখ্যাটি সত্যিই প্রাইম। প্রশ্ন হচ্ছে, আসলেই কি এত্তগুলো সংখ্যা দিয়ে ভাগ করেই একটা সংখ্যা প্রাইম নাকি সেটা বুঝতে হবে? চিন্তা করে দেখ, সংখ্যাটা যদি ছয় অঙ্কের একটা প্রাইম হয়ে থাকে, তাহলে তোমাকে কতবার ভাগ করে করে দেখতে হবে। নিশ্চয়ই এর থেকে ভালো কোনো পদ্ধতি আছে প্রাইম সংখ্যা বের করার! একটু চিন্তা করলে দেখতে পাবে যে, N/২ এর থেকে বড় কোন সংখ্যা কখনোই N কে ভাগ করতে পারে না। তাই ৭১ প্রাইম কি না, তা নিশ্চিত করতে ৩০ পর্যন্ত সংখ্যা দিয়ে ভাগ করলেই চলবে। কিন্তু এর থেকেও কমে কি করা যায়?

স্কয়ার রুটের জাদু
ধরি, একটা পূর্ণ সংখ্যা N কে ভাগ করে এমন একটি সংখ্যা হচ্ছে a। তাহলে N/a নিশ্চয়ই আরেকটি পূর্ণসংখ্যা হবে, ধরলাম সেটা b। N কে বর্গমূল করে যে সংখ্যাটি পেলাম সেটা ধরি c। তাহলে নিচের তিনটা ঘটনার কেবল একটাই সত্যি হওয়া সম্ভব—

১. a সংখ্যাটি c থেকে বড় কিন্ত b সংখ্যাটি c থেকে ছোট।
২. b সংখ্যাটি c থেকে বড় কিন্ত a সংখ্যাটি c থেকে ছোট।
৩. a ও b উভয়েই c এর সমান।

আমি যেই দাবিটা করছি সেটি কেন সত্যি সেটা খুব ইন্টারেস্টিং, তোমরা ভেবে বের কর। একটা বুদ্ধি দিই, c গুণ c হচ্ছে N।

ওপরের দাবি সত্যি হওয়ার কারণে আমাদের কিন্তু একটা লাভ হলো। লাভটা হচ্ছে, এখন আমরা যদি দেখতে চাই যে N প্রাইম কি না, তাহলে N কে কেবল ২ থেকে √N পর্যন্ত সংখ্যাগুলো দিয়ে ভাগ করার চেষ্টা করলেই চলবে। কারণ, যদি N মৌলিক না হয়েই থাকে, তবে অবশ্যই ২ থেকে √N এর মধ্যে N এর একটা ভাজক থাকবেই থাকবে।

সুতরাং, আমাদের হিসাব এখন আরও সহজ হয়ে গেল। এখন যদি আমরা ১০০০০০০ পর্যন্ত কোনো সংখ্যার মৌলিকতা প্রমাণ করতে চাই, তাহলে আমাদের সর্বোচ্চ ১০০০ পর্যন্ত সংখ্যা দিয়ে ভাগ দিলেই হবে।

সিভ অব ইরোতোসথেনিস
তোমাকে যদি বলা হয়, ১ থেকে ১০০ পর্যন্ত সবগুলো মৌলিক সংখ্যা বের কর, তাহলে তুমি কি করতে পার? আমরা একটু আগে যে পদ্ধতিতে একটা সংখ্যা মৌলিক কি না, বের করলাম। কিছুটা সেভাবেই কিন্তু কাজটা করা যায়। তোমার কাজ হবে একবারে একটা করে সংখ্যা নেওয়া এবং সেই সংখ্যাটিকে ওপরে বর্ণিত পদ্ধতিতে পরীক্ষা করা। তাহলে তোমাকে যদি ১ থেকে N পর্যন্ত সংখ্যার মৌলিকতা যাচাই করতে হয়, তাহলে প্রতিটা সংখ্যার জন্যই তোমাকে একটা করে লুপ চালাতে হবে। এখানে লুপ বলতে আমি বোঝাচ্ছি একই কাজ বারবার করাকে, আর সেই কাজটা হচ্ছে ২ থেকে√X পর্যন্ত সংখ্যাগুলো একটা একটা করে নিয়ে সেটাকে দিয়ে X কে ভাগ করার চেষ্টা করে দেখা। যদিও এই পদ্ধতিটি সঠিক, এর থেকেও কম ধাপে সমস্যাটি সমাধান করা যায়। গ্রিক গণিতবিদ ইরাতোসথেনিস খ্রিষ্টপূর্ব দ্বিতীয় শতকের দিকে এই পদ্ধতিটি আবিষ্কার করেছিলেন।

হাতেকলমে দেখে নেওয়া যাক, এই পদ্ধতিটি কীভাবে কাজ করে। মনে কর, তোমাকে ১ থেকে ২০ পর্যন্ত সংখ্যাগুলোর মৌলিকত্ব টেস্ট করতে হবে। তাহলে তুমি প্রথমে একটা জায়গায় ২০টা খালি বক্স আঁকো। শুরুতে সবগুলা বক্সই ফাঁকা। এই প্রতিটা বক্স একেকটি সংখ্যাকে প্রতিনিধিত্ব করে। প্রথম বক্সটি ১, দ্বিতীয়টি ২, এমন করে ২০ পর্যন্ত।

আমরা শুরুতেই জানি যে, ১ কোনো মৌলিক সংখ্যা নয়। তাই আমরা শুধু প্রথম বক্সটাকে কেটে ফেলব। তখন বক্সগুলো হবে নিচের মতো দেখতে:

এরপর আমরা ২ এর ঘরটাতে যাব। এই ঘরটা এখনো খালি, খালি থাকার অর্থ কী সেটা আমরা একটু পরেই বুঝতে পারব। এখন আমরা যেটা করব, ২ এর থেকে বড় ২ এর সবগুলো গুণিতকের ঘরগুলো কেটে ফেলব। এই গুণিতকগুলো হলো ৪, ৬, ৮, ১০, ১২, ১৪, ১৬, ১৮ এবং ২০। তাহলে বক্সগুলো দেখতে এখন এমন লাগবে:

দুইয়ের পরের ফাঁকা ঘরটি হচ্ছে তিনের। আগের মতো আমরা তিনের গুণিতকগুলোর ঘরগুলো কেটে ফেলব, বক্সগুলোর অবস্থা তখন হবে এমন:

এরপর আমরা যাব ৪–এর ঘরে। এই ঘরটা আগেই কাটা হয়ে গেছে। তাই আমরা এখানে কিছু না করে পাঁচের ঘরে চলে যাব। তারপর পাঁচের গুণিতকগুলোর ঘরগুলোকে কাটব। মজার ব্যাপার লক্ষ করবে যে, পাঁচ যে ঘরগুলো কাটতে গিয়েছিল। যেমন ১০, ১৫ ও ২০, এই ঘর তিনটি কিন্তু আগেই কাটা হয়ে গেছে।

এবার এক দফা যেই ঘরগুলোকে এখনো কাটা হয়নি, সেগুলোর দিকে তাকাও। ঘরগুলো হচ্ছে: ২, ৩, ৫, ৭, ১১, ১৩, ১৭ ও ১৯। এই সংখ্যাগুলোকে কি তোমার চেনা চেনা লাগছে? হ্যাঁ, এই সংখ্যাগুলোই হচ্ছে ২০ পর্যন্ত সব মৌলিক সংখ্যা। আর যে সংখ্যাগুলোর ঘর কাটা পড়েছে, সেগুলোর একটাও মৌলিক সংখ্যা নয়। একটু খেয়াল করলে দেখতে পাবে এই পদ্ধতিটি ব্যবহার করে আগের থেকে কম কষ্টেই আমরা একটা সীমা পর্যন্ত মৌলিক সংখ্যা বের করতে পেরেছি। এই পদ্ধতিটির নামই হচ্ছে ‘সিভ অব ইরাতোসথেনিস’।

হাতেকলমে এই কাজটা করা খুব সহজ। কিন্তু তোমাকে যদি অনেক বেশি সংখ্যা পর্যন্ত প্রাইম বের করতে বলা হয়, তবে সেটা বেশ কষ্টসাধ্য হবে। তখন তোমাকে এই কাজটাই প্রোগ্রামিংয়ের কোড লিখে সমাধান করতে হবে। সে জন্য আমাদের ওপরে বর্ণিত পদ্ধতিটি সুস্পষ্ট ধাপে লিখে ফেলতে হবে:

১. প্রথমে ১ থেকে N সংখ্যাগুলোর খালি বক্স নিয়ে ফেলি।
২. ১ নম্বর বক্সটি কেটে ফেলি, কারণ ১ সংখ্যাটি মৌলিক নয়।
৩. প্রথম মৌলিক সংখ্যা হচ্ছে ২, সংখ্যাটিকে হাতে রাখি। হাতের নাম দিলাম h।
৪. এই ধাপে ২ * h , ৩ * h , ৪ * h এভাবে করে N পর্যন্ত h এর সব গুণিতকের বক্সকে কেটে ফেলি।
৫. h এর পরের প্রথম খালি বক্সটাকে খুঁজে ফেলি, যদি না পাই তাহলে আমাদের কাজ শেষ, ধাপ ৬ এ চলে যাই। না হলে, হাতে থাকা সংখ্যার থেকে বড় প্রথম যে খালি বক্সটি খুঁজে পেলাম, সেটি h এ রাখি।
৬. এখনো যে ঘরগুলো কাটা হয়নি, সেগুলোই প্রাইম।

এখন তাহলে এই সমস্যাটাও সমাধান করে ফেলো: https://go.toph.co/correct-sieve-bn
সিভের সিপ্লাসপ্লাস কোড: https://go.toph.co/2NDrDzv

অনুশীলনী
আমরা আজকে যা যা শিখলাম, শুরুতেই সেটার কোড আমাদের নিজের হাতে খাতায় বা কম্পিউটারে লিখে ফেলতে হবে। প্রোগ্রামিং শেখার জন্য অনুশীলনের কোনো বিকল্প নেই। তাই তোমাকে অনুশীলেনের জন্য নিচে কিছু প্রবলেম দিলাম। ওহ, আরেকটা সমস্যাও নিজে সমাধান করার চেষ্টা করে দেখতে পার: ১৮৪৯ সালে গাউস বলেছিলেন ১ থেকে ৩০ লাখ সংখ্যা পর্যন্ত মৌলিক সংখ্যা আছে ২, ১৬, ৭৪৫টি। তোমাকে বলতে হবে, গাউস কি ঠিক বলেছিলেন? গাউসের কাছে আজকের মতো দ্রুতগতির কম্পিউটার ছিল না, ছিল না কোড করার মতো কোন প্রোগ্রামিং ভাষা। তুমিই তাহলে বলে দাও গাউস ঠিক ছিলেন কি না।

প্রবলেমের তালিকা:
https://go.toph.co/2UiAaca
https://go.toph.co/34dVx2W
https://go.toph.co/2zEa3mQ
https://go.toph.co/2LdwDcw


তারিফ এজাজ: সফটওয়্যার প্রকৌশলী, অবিচল আইটি