परिचय
आपने गैराज में लगी एक सेल से बेतरतीब कंप्यूटर पुर्ज़ों का बड़ा डिब्बा खरीदा। अब आप इन पुर्ज़ों को जोड़कर अपने लिए कस्टम कंप्यूटर बनाने लगे हैं।
आप जानना चाहते हैं कि पुर्ज़ों के अलग-अलग जोड़ मिलकर कैसा प्रदर्शन देते हैं। इसलिए आपने अपना खुद का बेंचमार्किंग प्रोग्राम बनाने का फैसला किया, ताकि पता चले कि आपके कंप्यूटरों का प्रदर्शन एक-दूसरे के मुकाबले कैसा है। इसके लिए आपने मशहूर "एराटोस्थनीज़ की छलनी" एल्गोरिदम चुना। यह बहुत पुराना एल्गोरिदम है, लेकिन यह आपके कंप्यूटरों को उनकी सीमा तक परख लेगा।
निर्देश
आपको एक प्रोग्राम बनाना है जो एराटोस्थनीज़ की छलनी का एल्गोरिदम लागू करके किसी दी गई संख्या से छोटी या उसके बराबर की सभी अभाज्य संख्याएँ ढूँढ निकाले।
अभाज्य संख्या वह संख्या होती है जो 1 से बड़ी है और सिर्फ 1 और खुद से विभाजित होती है।
जैसे 2, 3, 5, 7, 11 और 13 अभाज्य संख्याएँ हैं।
इसके उलट, 6 अभाज्य संख्या नहीं है, क्योंकि वह सिर्फ 1 और खुद से ही नहीं, बल्कि 2 और 3 से भी विभाजित होती है।
एराटोस्थनीज़ की छलनी का उपयोग करने के लिए सबसे पहले आप 2 और अपनी दी गई संख्या के बीच की सभी संख्याओं की एक सूची बनाइए।
इसके बाद नीचे दिए गए चरण बार-बार दोहराइए:
- अपनी सूची में अगली ऐसी संख्या ढूँढिए जिस पर चिह्न नहीं लगा है (चिह्न लगी संख्याओं को छोड़ते हुए)।
यह अभाज्य संख्या है।
- उस अभाज्य संख्या के सभी गुणजों को नहीं अभाज्य के रूप में चिह्नित कीजिए।
इन चरणों को तब तक दोहराते रहिए, जब तक आपकी सूची की हर संख्या पर काम पूरा न हो जाए।
अंत में जिन संख्याओं पर चिह्न नहीं लगा है, वे सभी अभाज्य होती हैं।
टेस्ट यह नहीं देखते कि आपने यह एल्गोरिदम लागू किया है या नहीं, वे सिर्फ यह देखते हैं कि आपने अभाज्य संख्याओं की सही सूची बनाई है या नहीं।
यह जाँचने के लिए कि आप छलनी सही तरीके से लागू कर रहे हैं, एक अच्छा पहला टेस्ट यह होगा कि आप देखें कि आप भाग या शेषफल की संक्रियाओं का उपयोग नहीं कर रहे हैं।
उदाहरण
मान लीजिए आप 10 से छोटी या उसके बराबर की अभाज्य संख्याएँ ढूँढ रहे हैं।
- 2, 3, 4, 5, 6, 7, 8, 9, 10 लिखिए और उन सभी पर कोई चिह्न न लगाइए।
- 2 पर चिह्न नहीं है, इसलिए यह अभाज्य है।
4, 6, 8 और 10 को "अभाज्य नहीं" के रूप में चिह्नित कीजिए।
- 3 पर चिह्न नहीं है, इसलिए यह अभाज्य है।
6 और 9 को अभाज्य नहीं के रूप में चिह्नित कीजिए (6 को चिह्नित करना ज़रूरी नहीं है, क्योंकि उस पर पहले ही चिह्न लग चुका है)।
- 4 पर "अभाज्य नहीं" का चिह्न लगा है, इसलिए हम उसे छोड़ देते हैं।
- 5 पर चिह्न नहीं है, इसलिए यह अभाज्य है।
10 को अभाज्य नहीं के रूप में चिह्नित कीजिए (ज़रूरी नहीं, क्योंकि उस पर पहले ही चिह्न लग चुका है)।
- 6 पर "अभाज्य नहीं" का चिह्न लगा है, इसलिए हम उसे छोड़ देते हैं।
- 7 पर चिह्न नहीं है, इसलिए यह अभाज्य है।
- 8 पर "अभाज्य नहीं" का चिह्न लगा है, इसलिए हम उसे छोड़ देते हैं।
- 9 पर "अभाज्य नहीं" का चिह्न लगा है, इसलिए हम उसे छोड़ देते हैं।
- 10 पर "अभाज्य नहीं" का चिह्न लगा है, इसलिए हम रुक जाते हैं, क्योंकि जाँचने के लिए और कोई संख्या नहीं बची।
आपने सभी संख्याओं को देख लिया और पाया कि 2, 3, 5 और 7 पर अभी भी कोई चिह्न नहीं है, यानी ये 10 से छोटी या उसके बराबर की अभाज्य संख्याएँ हैं।
