ভূমিকা
একটি গ্যারেজ সেলে আপনি কম্পিউটারের এলোমেলো যন্ত্রাংশের একটি বড় বাক্স কিনেছেন।
নিজের পছন্দমতো কম্পিউটার বানানোর জন্য আপনি যন্ত্রাংশগুলো জোড়া লাগাতে শুরু করেছেন।
বিভিন্ন সমন্বয়ে যন্ত্রাংশগুলো কেমন পারফর্ম করে তা আপনি পরীক্ষা করে দেখতে চান, তাই আপনার কম্পিউটারগুলো একে অন্যের তুলনায় কেমন তা বোঝার জন্য নিজেই একটি বেঞ্চমার্কিং প্রোগ্রাম বানানোর সিদ্ধান্ত নেন।
আপনি বেছে নেন বিখ্যাত "Sieve of Eratosthenes" অ্যালগরিদমটি। এটি প্রাচীন একটি অ্যালগরিদম, তবে আপনার কম্পিউটারকে সীমা পর্যন্ত ঠেলে দেবে।
নির্দেশনা
আপনার কাজ হলো এমন একটি প্রোগ্রাম তৈরি করা যা এরাটোস্থেনিসের সিভ অ্যালগরিদম ব্যবহার করে একটি নির্দিষ্ট সংখ্যার চেয়ে ছোট বা সমান সব মৌলিক সংখ্যা খুঁজে বের করে।
মৌলিক সংখ্যা হলো ১-এর চেয়ে বড় এমন একটি সংখ্যা, যা কেবল ১ এবং নিজে দিয়ে বিভাজ্য।
উদাহরণস্বরূপ, ২, ৩, ৫, ৭, ১১ এবং ১৩ মৌলিক সংখ্যা।
এর বিপরীতে, ৬ নয় একটি মৌলিক সংখ্যা, কারণ এটি কেবল ১ এবং নিজে দিয়ে নয়, ২ এবং ৩ দিয়েও বিভাজ্য।
এরাটোস্থেনিসের সিভ ব্যবহার করতে, প্রথমে ২ এবং আপনার নির্দিষ্ট সংখ্যার মধ্যবর্তী সব সংখ্যার একটি তালিকা তৈরি করুন।
এরপর নিচের ধাপগুলো বারবার পুনরাবৃত্তি করুন:
- আপনার তালিকা থেকে পরবর্তী চিহ্নিত-না-করা সংখ্যাটি খুঁজুন (চিহ্নিত সংখ্যাগুলো এড়িয়ে যান)।
এটি একটি মৌলিক সংখ্যা।
- ওই মৌলিক সংখ্যার সব গুণিতককে মৌলিক নয় হিসেবে চিহ্নিত করুন।
আপনার তালিকার প্রতিটি সংখ্যা শেষ না হওয়া পর্যন্ত আপনি এই ধাপগুলো বারবার করতে থাকুন।
শেষে, চিহ্নিত না করা সব সংখ্যাই মৌলিক।
টেস্টগুলো এটা যাচাই করে না যে আপনি অ্যালগরিদমটি সঠিকভাবে বাস্তবায়ন করেছেন কি না, শুধু এটা দেখে যে আপনি সঠিক মৌলিক সংখ্যার তালিকা বের করতে পেরেছেন কি না।
আপনি সিভটি ঠিকভাবে বাস্তবায়ন করছেন কি না তা যাচাই করতে, ভালো একটি প্রথম পরীক্ষা হলো এটা দেখা যে আপনি ভাগ বা ভাগশেষের অপারেশন ব্যবহার করছেন না।
উদাহরণ
ধরা যাক, আপনি ১০-এর চেয়ে ছোট বা সমান মৌলিক সংখ্যাগুলো খুঁজছেন।
- ২, ৩, ৪, ৫, ৬, ৭, ৮, ৯, ১০ তালিকাভুক্ত করুন, সবগুলোকে চিহ্নিত-না-করা রেখে দিন।
- ২ চিহ্নিত নয়, তাই এটি একটি মৌলিক সংখ্যা।
৪, ৬, ৮ এবং ১০-কে "মৌলিক নয়" হিসেবে চিহ্নিত করুন।
- ৩ চিহ্নিত নয়, তাই এটি একটি মৌলিক সংখ্যা।
৬ এবং ৯-কে মৌলিক নয় হিসেবে চিহ্নিত করুন (৬ চিহ্নিত করা ঐচ্ছিক - এটি ইতিমধ্যে চিহ্নিত হয়ে গেছে)।
- ৪-কে "মৌলিক নয়" হিসেবে চিহ্নিত করা হয়েছে, তাই আমরা এটি এড়িয়ে যাই।
- ৫ চিহ্নিত নয়, তাই এটি একটি মৌলিক সংখ্যা।
১০-কে মৌলিক নয় হিসেবে চিহ্নিত করুন (ঐচ্ছিক - এটি ইতিমধ্যে চিহ্নিত হয়ে গেছে)।
- ৬-কে "মৌলিক নয়" হিসেবে চিহ্নিত করা হয়েছে, তাই আমরা এটি এড়িয়ে যাই।
- ৭ চিহ্নিত নয়, তাই এটি একটি মৌলিক সংখ্যা।
- ৮-কে "মৌলিক নয়" হিসেবে চিহ্নিত করা হয়েছে, তাই আমরা এটি এড়িয়ে যাই।
- ৯-কে "মৌলিক নয়" হিসেবে চিহ্নিত করা হয়েছে, তাই আমরা এটি এড়িয়ে যাই।
- ১০-কে "মৌলিক নয়" হিসেবে চিহ্নিত করা হয়েছে, তাই আর যাচাই করার কোনো সংখ্যা নেই বলে আমরা থেমে যাই।
আপনি সব সংখ্যা পরীক্ষা করেছেন এবং দেখলেন ২, ৩, ৫ এবং ৭ এখনো চিহ্নিত নয়, অর্থাৎ এগুলোই ১০-এর চেয়ে ছোট বা সমান মৌলিক সংখ্যা।
