সংখ্যাতত্ত্বের অসাধারণ সৌন্দর্য্য আর বহুমাত্রিক ব্যবহারের কারণে প্রাইম নাম্বার গণিত আর কম্পিউটার বিজ্ঞানে বেশ আলোচিত একটি বিষয়। সেই ক্লাস টু থেকেই মৌলিক সংখ্যা সম্পর্কে আমরা জানি। একদম প্রাইমারি স্কুলের সময়ে আমরা প্রাইম নাম্বার সম্পর্কে যা শিখেছি তা হলো এরকম – যে সকল ধনাত্মক পূর্ণ সংখ্যাকে ১ ও ঐ সংখ্যাটি ব্যতীত অন্য কোন সংখ্যা দিয়ে নিঃশেষে ভাগ করা যায় না, সেসব সংখ্যাই হল প্রাইম সংখ্যা। যেমন – ১, ৩, ৫, ৭, ১১… ইত্যাদি। প্রাইম সংখ্যার অন্যতম মৌলিক বৈশিষ্ট্য হলো এর প্রকৃত ভাজক সংখ্যা হবে স্ট্রিক্টলি দুটো। ঠিক এই কারণেই ১ কে প্রাইম নাম্বার হিসেবে কাউন্ট করা হয় না। কারণ ১ ব্যতীত এর অন্য কোন ভাজক নেই। অন্যদিকে ৫ এর ভাজক দুটি (১ ও ৫) বিধায় ৫ একটি প্রাইম সংখ্যা । ৬ প্রাইম সংখ্যা না কারণ ৬ এর ভাজক ৪ টি (১, ২, ৩, ৬)।
প্রাইম নাম্বার চেকিংয়ের বেশ কিছু উপায় আছে। এলগরিদম কমপ্লেক্সিটি উপর ভিত্তি করে নানাভাবে প্রাইমারিলিটি টেস্টিং এর কোড করা সম্ভব। এর মাঝে সবচে জনপ্রিয় ও পুরাতন এলগরিদম হলো সিভ অব এরাটস্থেনিজ। সিভ অব এরাটস্থেনিজকে মডিফিকেশন করে বিটওয়াইজ সিভ, সেগমেন্টেড সিভ কন্সেপ্ট দিয়ে অনেক অনেক বড় বড় সংখ্যা প্রাইম কিনা সেটি নির্ণয় করা সম্ভব।
এই লেখায় আমি দুটো উপায় নিয়ে আলোচনা করবো। একটি সিম্পল মেথড অন্যটি সিভ অব এরাটস্থেনিজ এলগরিদম।
ব্রুটফোর্স ক্যালকুলেশন
প্রাইম নাম্বার চেক করার ব্রুট ফোর্স এপ্রোচ হলো ২ থেকে সংখ্যাটির সংখ্যাটির বর্গমূলের চেয়ে ছোট সংখ্যা দ্বারা পর্যায়ক্রমে ভাগ করা। এই সীমার মাঝে কোন সংখ্যা দ্বারা যদি আমাদের নির্ণেয় সংখ্যাটি নিঃশেষে বিভাজ্য না হয়, তাহলে সংখ্যাটিকে প্রাইম বলা যায়, নইলে সংখ্যাটি একটি যৌগিক সংখ্যা। এর এপ্রোচের লজিক প্রাইম নাম্বারের ডেফিনিশন দেখলেই বুঝা যায়। কারণ কোন সংখ্যাকে তার বর্গমুলের চেয়ে বড় সংখ্যা দ্বারা প্রকৃত ভাজক রেখে ভাগ করা সম্ভব না। তাই রেঞ্জের সংখ্যাগুলো দিয়ে চেক করলেই ফলাফল পাওয়া সম্ভব। আমরা জানি, সেসব সংখ্যাই প্রাইম সংখ্যা যাদেরকে সংখ্যাটির বর্গমূলের সমান বা ছোটো কোনো প্রাইম দিয়ে ভাগ করা যায় না। ঠিক এই কারণেই, নিচের কোডে n পর্যন্ত লুপ না চালিয়ে sqrt(n) পর্যন্ত লুপ চালানো হয়েছে।
এই মেথডটি লুপ আইটারেশনের পরিমাণ sqrt(n)। প্রতিবার প্রাইম চেক করার ক্ষেত্রে sqrt(n) পর্যন্ত লুপ ঘুরবে যার কমপ্লেক্সিটি সিভ অব এরাটস্থেনিজ থেকে অনেক বেশী। বড় সংখ্যার প্রাইমারিলিটি চেক করতে গেলে এই মেথড খুব একটা সুবিধার না।
সিভ এলগরিদমিক ক্যালকুলেশন
এরাটস্থেনিজ ছিলেন একজন গ্রিক গণিতবিদ। তিনিই সর্বপ্রথম ১৯৩৪ সালে দ্রুত প্রাইম বের করার জন্য প্রাইম নাম্বারস সিভ এলগরিদমটি প্রকাশ করেন। প্রাইম সিভ একটি নির্দিষ্ট সীমার মাঝে ধারাবাহিকভাবে যৌগিক সংখ্যাগুলোকে বাদ দিয়ে মৌলিক সংখ্যাগুলোকে ছেকে বের করে । এটি পুরোপুরি প্রগ্রেসিভ একটি মেথড । এখন পর্যন্ত বড় রেঞ্জের সংখ্যার প্রাইমারিলিটি চেক করার জন্যে এটিই সবচে কার্যকর এবং এফিশিয়েন্ট এলগরিদম ।
উপরের গিফ ইমেজটি ভালোভাবে লক্ষ করলে মূল প্রসেসটা সহজেই ধরা যায়। এটিকে একটি ছাঁকনি হিসেবে কল্পনা করো। অনেকগুলা সংখ্যা বাদ পড়ছে আর কিছু সংখ্যা ডানপাশে জমা হচ্ছে। এই ডানপাশের সংখ্যাগুলোই আমাদের কাঙ্ক্ষিত প্রাইম সংখ্যার তালিকা। প্রথমে ২ কে প্রাইম হিসেবে নিচ্ছে, তারপর দুইয়ের সবগুলো গুণনীয়ককে ছাঁকনীতে ছেঁকে বাদ দেয়া হচ্ছে। ২ একমাত্র জোড় প্রাইম সংখ্যা কারণ বাকি জোড় সংখ্যাগুলো সব কম্পোজিট সংখ্যা। তারপর ৩ কে প্রাইম হিসেবে নেয়া হয়েছে এবং ৩ এর সকল গুণনীয়ককে বাদ দেয়া হয়েছে। একইভাবে ৫, ৭, ১১… এভাবে ১২০ পর্যন্ত মোট প্রাইম সংখ্যা পাওয়া গেছে ৩০ টি।
গুণনীয়কগুলো বাদ দেয়ার কারণ হলো এদের প্রকৃত ভাজক সংখ্যা সবসময় দুইয়ের চেয়ে বড় হয়, আর যাদের ভাজক সংখ্যা দুইয়ের চেয়ে বেশী তাদেরকে তো প্রাইম ধরা যাবে না।
কোডের পাশে যেসব জায়াগায় খটকা লাগার কথা সেখানে কমেন্টিং করা আছে। ভালোভাবে খ্যাল করলে বুঝতে সমস্যা হবার কথা না। এখনও যদি বুঝতে সমস্যা হয়, তাহলে রেফারেন্স লিঙ্কগুলো দেখো।
রেফারেন্স লিঙ্ক
- ন্যূনতম সংখ্যাতত্ত্ব।প্রোগক্রিয়া
- প্রাইম জেনারেটর(সিভ এলগরিদম)। শাফায়েত ভাইয়ের ব্লগ
- প্রাইম নাম্বার সিভ অব এরাটেস্থেনিজ। বাইনারি রঙ্গ
রিলেটেড প্রবলেম লিঙ্কঃ
- UVa 543 – Goldbach’s Conjecture
- UVa 686 – Goldbach’s Conjecture (II)
- UVa 10394 – Twin Prime
- UVa 10533 – Digit Primes