छलनी

निर्देश

आपको एक ऐसा प्रोग्राम बनाना है जो एराटोस्थनीज़ की छलनी एल्गोरिदम लागू करके किसी दी गई संख्या से कम या उसके बराबर की सभी अभाज्य संख्याएँ खोज निकाले।

अभाज्य संख्या वह संख्या है जो 1 से बड़ी होती है और केवल 1 और खुद से विभाज्य होती है। उदाहरण के लिए, 2, 3, 5, 7, 11 और 13 अभाज्य संख्याएँ हैं। इसके विपरीत, 6 अभाज्य संख्या नहीं है, क्योंकि यह केवल 1 और खुद से ही विभाज्य नहीं होती, बल्कि 2 और 3 से भी विभाज्य होती है।

एराटोस्थनीज़ की छलनी का उपयोग करने के लिए सबसे पहले 2 से लेकर अपनी दी गई संख्या तक (उस संख्या को भी शामिल करते हुए) सभी संख्याएँ लिखिए। फिर इन चरणों का पालन कीजिए:

1. अगली बिना निशान वाली संख्या ढूँढ़िए (निशान लगी संख्याओं को छोड़ते हुए)। यह अभाज्य संख्या होती है।
2. उस अभाज्य संख्या के सभी गुणजों पर अभाज्य नहीं का निशान लगाइए।

इन चरणों को तब तक दोहराइए जब तक आप हर संख्या को देख न लें। अंत में, जिन संख्याओं पर निशान नहीं लगा है, वे सभी अभाज्य होती हैं।

उदाहरण

मान लीजिए आप 10 से कम या उसके बराबर अभाज्य संख्याएँ ढूँढ़ रहे हैं।

• 2, 3, 4, 5, 6, 7, 8, 9, 10 लिखिए और उन सबको बिना निशान के छोड़ दीजिए।

  2 3 4 5 6 7 8 9 10
  

• 2 पर निशान नहीं है, इसलिए यह अभाज्य है। 4, 6, 8 और 10 पर "अभाज्य नहीं" का निशान लगाइए।

  2 3 [4] 5 [6] 7 [8] 9 [10]
  ↑
  

• 3 पर निशान नहीं है, इसलिए यह अभाज्य है। 6 और 9 पर अभाज्य नहीं का निशान लगाइए (6 पर निशान लगाना ज़रूरी नहीं है, क्योंकि उस पर पहले ही निशान लग चुका है)।

  2 3 [4] 5 [6] 7 [8] [9] [10]
    ↑
  

• 4 पर "अभाज्य नहीं" का निशान लगा है, इसलिए हम उसे छोड़ देते हैं।

  2 3 [4] 5 [6] 7 [8] [9] [10]
       ↑
  

• 5 पर निशान नहीं है, इसलिए यह अभाज्य है। 10 पर अभाज्य नहीं का निशान लगाइए (ज़रूरी नहीं है, क्योंकि उस पर पहले ही निशान लग चुका है)।

  2 3 [4] 5 [6] 7 [8] [9] [10]
          ↑
  

• 6 पर "अभाज्य नहीं" का निशान लगा है, इसलिए हम उसे छोड़ देते हैं।

  2 3 [4] 5 [6] 7 [8] [9] [10]
             ↑
  

• 7 पर निशान नहीं है, इसलिए यह अभाज्य है।

  2 3 [4] 5 [6] 7 [8] [9] [10]
                ↑
  

• 8 पर "अभाज्य नहीं" का निशान लगा है, इसलिए हम उसे छोड़ देते हैं।

  2 3 [4] 5 [6] 7 [8] [9] [10]
                   ↑
  

• 9 पर "अभाज्य नहीं" का निशान लगा है, इसलिए हम उसे छोड़ देते हैं।

  2 3 [4] 5 [6] 7 [8] [9] [10]
                       ↑
  

• 10 पर "अभाज्य नहीं" का निशान लगा है, इसलिए हम रुक जाते हैं क्योंकि जाँचने के लिए और कोई संख्या नहीं बची।

  2 3 [4] 5 [6] 7 [8] [9] [10]
                           ↑
  

आपने सभी संख्याएँ देख लीं और पाया कि 2, 3, 5 और 7 पर अभी भी निशान नहीं है, यानी ये 10 से कम या उसके बराबर अभाज्य संख्याएँ हैं।

---

स्रोत

Wikipedia पर एराटोस्थनीज़ की छलनी