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