Sieve of Eratosthenes (एरातोस्थनीज छलनी)
नंबर
n से छोटे सभी अभाज्य संख्याओं को ढूंढने का यह तरीका, हर एक संख्या की प्राइमलिटी (अभाज्यता) जाँचने से कहीं तेज़ है। हम हर संख्या को जाँचने के बजाय उन सभी संख्याओं को पहले से हटा सकते हैं जो आगे चलकर प्राइम बनने वाली नहीं हैं।
शुरुआत में, हम 2 से लेकर
n तक की सभी संख्याओं को “संभवतः प्राइम” के रूप में चिह्नित कर सकते हैं। उसके बाद, हम 2 के सभी गुणकों को हटाकर 2 को “निश्चित रूप से प्राइम” घोषित कर देते हैं। आगे 3 के सभी गुणकों को हटाकर 3 को “निश्चित रूप से प्राइम” कहते हैं। 4 को हम छोड़ देते हैं क्योंकि इसको 2 को प्रोसेस करते समय पहले ही हटा दिया गया था। अगली संख्या 5 को लेते हैं और उसके सभी गुणकों को भी हटा देते हैं। 6 फिर से वही कारण होने से पहले ही “प्राइम नहीं” चिह्नित हो चुका है (2 के गुणक के तौर पर)। इसी तरह हम यह प्रक्रिया n तक जारी रख सकते हैं।एल्गोरिथ्म के दिलचस्प गुण और अनुकूलन
जब हम किसी प्राइम नंबर
p के सभी गुणकों को “संभवतः प्राइम” वाली सूची से हटाते जाते हैं (शुरू 2 से करते हुए), तो बड़े लाभ के रूप में हमें पूरा क्रम 2·p, 3·p, 4·p, 5·p... देखने की ज़रूरत नहीं पड़ती। इसकी बजाय हम सीधे p·p से शुरू कर सकते हैं। ऐसा इसलिए क्योंकि p के जो भी गुणक 2·p, 3·p, 4·p, 5·p वगैरह हैं, वे पहले ही तब हट चुके होते हैं जब हम दो, तीन, पाँच आदि प्राइम संख्याओं पर प्रक्रिया चला रहे थे। इसीलिए p के गुणकों में से पहला ऐसा नंबर जो अभी तक नहीं हटाया गया है, वह p·p होता है।उदाहरण के लिए, जब हम
p=3 पर आते हैं, तो हम सीधा 9 से शुरू करते हैं, क्योंकि 6 को 2 पर प्रोसेस करते समय ही “प्राइम नहीं” के रूप में चिह्नित कर दिया गया था। इसी तरह p=5 पर आने पर हम 25 से शुरू करते हैं, क्योंकि 10 (10 = 2·5) पहले 2 पर प्रोसेस के दौरान हट गया था, 15 (15 = 3·5) 3 पर हट गया था, और 20 (20 = 4·5) भी 2 पर प्रोसेस के समय हट चुका था।prime = [True] * n # prime[i] = True => i एक प्राइम संख्या है
prime[0] = prime[1] = False # 0 और 1 प्राइम नहीं हैं
for i in range(2, n): # 2 से n तक लूप
if prime[i]: # अगर i प्राइम है => i के सभी गुणकों को प्राइम नहीं चिह्नित करें
for j in range(i * i, n, i): # हम i * i से लूप शुरू करते हैं क्योंकि i से छोटे i के गुणक पहले ही हट चुके हैं
prime[j] = Falsen.मान लें हम n=100 के लिए यह प्रक्रिया चलाएँ:
prime = [False, False, True, True, ..., True] (साइज़ 100)i = 2⇒prime[2] = True⇒for j in 4, 6, 8, ... 100औरprime[j]=Falseचिह्नित करें
i = 3⇒prime[3] = True⇒for j in 9, 12, ... 100औरprime[j]=Falseचिह्नित करें
i = 4⇒prime[4] = False
i = 5⇒prime[5] = True⇒for j in 25, 30, ... 100औरprime[j]=Falseचिह्नित करें
i = 6⇒prime[6] = False
i = 7⇒prime[7] = True⇒for j in 49, 56, ... 100औरprime[j]=Falseचिह्नित करें
i = 8⇒prime[8] = False
i = 9⇒prime[9] = False
i = 10⇒prime[10] = False
i = 11⇒prime[11] = True⇒for j in [empty]औरprime[j]=Falseचिह्नित करें
- यहाँ हम रुक सकते हैं क्योंकि
i * iपहले हीnसे बड़ा हो गया है। इसलिए इसके बाद किसी प्राइम संख्या कोFalseचिह्नित करने की ज़रूरत नहीं पड़ेगी। अब हम सूची में रह गए प्राइम संख्याओं को निकालकर 100 से छोटे सभी प्राइम प्रिंट कर सकते हैं।
यह तरीका काफी तेज़ है और लगभग क्रियाएँ करता है। यह वाकई बहुत बड़ा सुधार है! ऑपरेशनों के बजाय अगर ऑपरेशनों की बात करें, तो इसका अंतर बहुत बड़ा हो जाता है। उसी उदाहरण पर वापस जाएँ जिसमें किसी एल्गोरिथ्म को
n ऑपरेशनों में 10 साल (3650 दिन) लगते, या ऑपरेशनों में 2 महीने (61 दिन) लगते, वहाँ ऑपरेशनों पर उसे 4 दिन से भी कम लगेंगे!एक और अनुकूलन, जो सिमुलेशन में भी उल्लेखित है, वह यह है कि बाहरी लूप में
i को 2 से लेकर तक ही चलाएँ, क्योंकि भीतरी लूप i·i से शुरू होता है, और इसीलिए n से बड़ी किसी संख्या के लिए भीतरी लूप में prime[j] = False करने की ज़रूरत ही नहीं आएगी (भीतरी लूप की ऊपरी सीमा n है)।इनपुट
इनपुट की पहली पंक्ति में एक एकल पूर्णांक
n (2 ≤ n ≤ ) दिया होता है।आउटपुट
कार्यक्रम को
n से छोटी या बराबर सभी प्राइम संख्याओं को प्रिंट करना चाहिए।Examples
इनपुट | आउटपुट |
8 | 2 3 5 7 |
17 | 2 3 5 7 11 13 17 |
19 | 2 3 5 7 11 13 17 19 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB