एराटोस्थनीज की छलनी: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{short description|Ancient algorithm for generating prime numbers}}
{{short description|Ancient algorithm for generating prime numbers}}
{{For|the sculpture|The Sieve of Eratosthenes (sculpture)}}
{{For|the sculpture|The Sieve of Eratosthenes (sculpture)}}
[[File:Animation Sieve of Eratosth.gif|right|frame|एराटोस्थनीज की छलनी: 121 से नीचे के अभाज्यों के लिए एल्गोरिथम चरण (प्राइम के वर्ग से शुरू करने के अनुकूलन सहित)।]]गणित में, एराटोस्थनीज की छलनी किसी भी सीमा तक सभी [[अभाज्य संख्या]]ओं को खोजने के लिए एक प्राचीन [[ कलन विधि ]] है।
[[File:Animation Sieve of Eratosth.gif|right|frame|एराटोस्थनीज की छलनी: 121 से नीचे के अभाज्यों के लिए एल्गोरिथम चरण (प्राइम के वर्ग से प्रारम्भ करने के अनुकूलन सहित)।]]गणित में, एराटोस्थनीज की छलनी किसी भी सीमा तक सभी [[अभाज्य संख्या]]ओं को की शोध के लिए प्राचीन [[ कलन विधि ]] है।


यह पुनरावृत्त रूप से [[समग्र संख्या]] (अर्थात, अभाज्य नहीं) के रूप में चिह्नित करता है, प्रत्येक अभाज्य संख्या के गुणकों को, पहले अभाज्य संख्या के साथ शुरू करता है, 2। किसी दिए गए अभाज्य के गुणकों को अंकगणित के साथ उस अभाज्य से शुरू होने वाली संख्याओं के अनुक्रम के रूप में उत्पन्न किया जाता है। प्रगति जो उस प्रधान के बराबर है।<ref name="horsley">Horsley, Rev. Samuel, F. R. S., "''{{lang|el|Κόσκινον Ερατοσθένους}}'' or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," [https://www.jstor.org/stable/106053 ''Philosophical Transactions'' (1683–1775), Vol. 62. (1772), pp. 327–347].</ref> प्रत्येक अभाज्य द्वारा विभाज्यता के लिए प्रत्येक उम्मीदवार संख्या का क्रमिक रूप से परीक्षण करने के लिए [[ परीक्षण प्रभाग ]] का उपयोग करने से छलनी का यह महत्वपूर्ण अंतर है।<ref name="ONeill" />एक बार प्रत्येक खोजे गए प्राइम के सभी गुणकों को कंपोजिट के रूप में चिह्नित किया गया है, शेष अचिह्नित संख्याएं प्राइम हैं।
यह पुनरावृत्त रूप से [[समग्र संख्या]] (अर्थात, अभाज्य नहीं) के रूप में चिह्नित करता है, प्रत्येक अभाज्य संख्या के गुणकों को, प्रथम अभाज्य संख्या 2 के साथ प्रारम्भ करता है, । किसी दिए गए अभाज्य के गुणकों को अंकगणित के साथ उस अभाज्य से प्रारम्भ होने वाली संख्याओं के अनुक्रम के रूप में उत्पन्न किया जाता है। प्रगति जो उस प्रधान के समान है।<ref name="horsley">Horsley, Rev. Samuel, F. R. S., "''{{lang|el|Κόσκινον Ερατοσθένους}}'' or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," [https://www.jstor.org/stable/106053 ''Philosophical Transactions'' (1683–1775), Vol. 62. (1772), pp. 327–347].</ref> प्रत्येक अभाज्य द्वारा विभाज्यता के लिए प्रत्येक उम्मीदवार संख्या का क्रमिक रूप से परीक्षण करने के लिए [[ परीक्षण प्रभाग ]] का उपयोग करने से छलनी महत्वपूर्ण है।<ref name="ONeill" /> प्रत्येक अनुशोधित प्राइम के सभी गुणकों को कंपोजिट के रूप में चिह्नित किया गया है, शेष अचिह्नित संख्याएं प्राइम हैं।


छलनी का सबसे पहला ज्ञात संदर्भ ({{lang-grc|κόσκινον Ἐρατοσθένους}}, कोस्किनॉन एराटोस्थेनस) अंकगणित के [[निकोमाचस]] के परिचय में है,<ref name=nicomachus>{{citation|editor-first=Richard|editor-last=Hoche|editor-link=Richard Hoche|title=Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, chapter XIII, 3|year=1866|location= Leipzig|publisher= B.G. Teubner|page=30|url=https://archive.org/stream/nicomachigerasen00nicouoft#page/30/mode/2up}}</ref> एक प्रारंभिक 2 सेंट। CE पुस्तक जो इसका श्रेय एराटोस्थनीज को देती है, जो कि एक तीसरा प्रतिशत है। बीसीई [[ग्रीक गणित]], हालांकि अभाज्य संख्याओं के बजाय विषम संख्याओं द्वारा छलनी का वर्णन करता है।<ref name=nicomachus1926>{{citation|author=Nicomachus of Gerasa|title=Introduction to Arithmetic; translated into English by Martin Luther D'Ooge ; with studies in Greek arithmetic by Frank Egleston Robbins and Louis Charles Karpinski, chapter XIII, 3|year=1926|location=New York|publisher=The Macmillan Company|page=204}}</ref>
छलनी का सबसे प्रथम ज्ञात संदर्भ ({{lang-grc|κόσκινον Ἐρατοσθένους}}, कोस्किनॉन एराटोस्थेनस) अंकगणित के [[निकोमाचस]] के परिचय में,<ref name=nicomachus>{{citation|editor-first=Richard|editor-last=Hoche|editor-link=Richard Hoche|title=Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, chapter XIII, 3|year=1866|location= Leipzig|publisher= B.G. Teubner|page=30|url=https://archive.org/stream/nicomachigerasen00nicouoft#page/30/mode/2up}}</ref> प्रारंभिक 2 सेंट है। CE पुस्तक जो इसका श्रेय एराटोस्थनीज को देती है, जो कि तीसरा प्रतिशत है। बीसीई [[ग्रीक गणित]], चूँकि अभाज्य संख्याओं के अतिरिक्त विषम संख्याओं द्वारा छलनी का वर्णन करता है।<ref name=nicomachus1926>{{citation|author=Nicomachus of Gerasa|title=Introduction to Arithmetic; translated into English by Martin Luther D'Ooge ; with studies in Greek arithmetic by Frank Egleston Robbins and Louis Charles Karpinski, chapter XIII, 3|year=1926|location=New York|publisher=The Macmillan Company|page=204}}</ref>
कई जनरेटिंग प्राइम्स में से एक#प्राइम सीवेस, यह सभी छोटे प्राइम्स को खोजने के सबसे कुशल तरीकों में से एक है। इसका उपयोग अंकगणितीय प्रगति में अभाज्य संख्याएँ खोजने के लिए किया जा सकता है।<ref>J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", [https://www.jstor.org/stable/1967477 ''Annals of Mathematics, Second Series'' '''10''':2 (1909), pp. 88–104].</ref>
कई जनरेटिंग प्राइम्स में से प्राइम सीवेस, यह सभी छोटे प्राइम्स की शोध के सबसे कुशल उपाय है। इसका उपयोग अंकगणितीय प्रगति में अभाज्य संख्या की अनुशोधन के लिए किया जा सकता है।<ref>J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", [https://www.jstor.org/stable/1967477 ''Annals of Mathematics, Second Series'' '''10''':2 (1909), pp. 88–104].</ref>




Line 14: Line 14:
एक अभाज्य संख्या एक [[प्राकृतिक संख्या]] है जिसमें दो अलग-अलग प्राकृतिक संख्या वि[[भाजक]] होते हैं: संख्या [[1]] और स्वयं।
एक अभाज्य संख्या एक [[प्राकृतिक संख्या]] है जिसमें दो अलग-अलग प्राकृतिक संख्या वि[[भाजक]] होते हैं: संख्या [[1]] और स्वयं।


किसी दिए गए पूर्णांक से कम या उसके बराबर सभी अभाज्य संख्याएँ ज्ञात करना {{mvar|n}} एराटोस्थनीज की विधि द्वारा:
किसी दिए गए पूर्णांक से कम या उसके समान  सभी अभाज्य संख्याएँ ज्ञात करना {{mvar|n}} एराटोस्थनीज की विधि द्वारा:


# 2 से लगातार पूर्णांकों की सूची बनाएं {{mvar|n}}: {{math|(2, 3, 4, ..., ''n'')}}.
# 2 से लगातार पूर्णांकों की सूची बनाएं {{mvar|n}}: {{math|(2, 3, 4, ..., ''n'')}}.
# शुरू में, चलो {{mvar|p}} बराबर 2, सबसे छोटी अभाज्य संख्या।
# प्रारम्भ में, चलो {{mvar|p}} समान  2, सबसे छोटी अभाज्य संख्या।
# के गुणजों की गणना करें {{mvar|p}} की वृद्धि में गिनती करके {{mvar|p}} से {{math|2''p''}} को {{mvar|n}}, और उन्हें सूची में चिह्नित करें (ये होंगे {{math|2''p'', 3''p'', 4''p'', ...}}; {{mvar|p}} खुद को चिह्नित नहीं किया जाना चाहिए)।
# के गुणजों की गणना करें {{mvar|p}} की वृद्धि में गिनती करके {{mvar|p}} से {{math|2''p''}} को {{mvar|n}}, और उन्हें सूची में चिह्नित करें (ये होंगे {{math|2''p'', 3''p'', 4''p'', ...}}; {{mvar|p}} खुद को चिह्नित नहीं किया जाना चाहिए)।
# सूची में सबसे छोटी संख्या का पता लगाएं {{mvar|p}} जो चिह्नित नहीं है। अगर ऐसी कोई संख्या नहीं थी, तो रुकें। नहीं तो जाने दो {{mvar|p}} अब इस नई संख्या के बराबर करें (जो अगला अभाज्य है), और चरण 3 से दोहराएं।
# सूची में सबसे छोटी संख्या का पता लगाएं {{mvar|p}} जो चिह्नित नहीं है। अगर ऐसी कोई संख्या नहीं थी, तो रुकें। नहीं तो जाने दो {{mvar|p}} अब इस नई संख्या के समान  करें (जो अगला अभाज्य है), और चरण 3 से दोहराएं।
# जब एल्गोरिथम समाप्त हो जाता है, तो सूची में चिह्नित नहीं की गई शेष संख्याएँ नीचे दी गई सभी अभाज्य संख्याएँ होती हैं {{mvar|n}}.
# जब एल्गोरिथम समाप्त हो जाता है, तो सूची में चिह्नित नहीं की गई शेष संख्याएँ नीचे दी गई सभी अभाज्य संख्याएँ होती हैं {{mvar|n}}.


यहाँ मुख्य विचार यह है कि प्रत्येक मान दिया गया है {{mvar|p}} प्राइम होगा, क्योंकि अगर यह कंपोजिट होता तो इसे किसी अन्य, छोटे प्राइम के मल्टीपल के रूप में चिह्नित किया जाता। ध्यान दें कि कुछ संख्याओं को एक से अधिक बार चिह्नित किया जा सकता है (उदाहरण के लिए, 15 को 3 और 5 दोनों के लिए चिह्नित किया जाएगा)।
यहाँ मुख्य विचार यह है कि प्रत्येक मान दिया गया है {{mvar|p}} प्राइम होगा, क्योंकि अगर यह कंपोजिट होता तो इसे किसी अन्य, छोटे प्राइम के मल्टीपल के रूप में चिह्नित किया जाता। ध्यान दें कि कुछ संख्याओं को एक से अधिक बार चिह्नित किया जा सकता है (उदाहरण के लिए, 15 को 3 और 5 दोनों के लिए चिह्नित किया जाएगा)।


परिशोधन के रूप में, चरण 3 में से शुरू करके संख्याओं को चिह्नित करना पर्याप्त है {{math|''p''<sup>2</sup>}}, के सभी छोटे गुणकों के रूप में {{mvar|p}} उस बिंदु पर पहले ही चिह्नित किया जा चुका होगा। इसका मतलब है कि एल्गोरिदम को चरण 4 में समाप्त करने की अनुमति है जब {{math|''p''<sup>2</sup>}} से बड़ा है {{mvar|n}}.<ref name="horsley" />  
परिशोधन के रूप में, चरण 3 में से प्रारम्भ करके संख्याओं को चिह्नित करना पर्याप्त है {{math|''p''<sup>2</sup>}}, के सभी छोटे गुणकों के रूप में {{mvar|p}} उस बिंदु पर प्रथम ही चिह्नित किया जा चुका होगा। इसका मतलब है कि एल्गोरिदम को चरण 4 में समाप्त करने की अनुमति है जब {{math|''p''<sup>2</sup>}} से बड़ा है {{mvar|n}}.<ref name="horsley" />  
एक और परिशोधन शुरू में केवल विषम संख्याओं को सूचीबद्ध करना है, {{math|(3, 5, ..., ''n'')}}, और की वृद्धि में गिनें {{math|2''p''}} चरण 3 में, इस प्रकार केवल विषम गुणकों को चिह्नित करना {{mvar|p}}. यह वास्तव में मूल एल्गोरिदम में दिखाई देता है।<ref name="horsley" /><ref name="nicomachus1926" />  इसे पहिया गुणनखंड के साथ सामान्यीकृत किया जा सकता है, प्रारंभिक सूची को केवल पहले कुछ अभाज्य संख्याओं के सह-अभाज्य से बनाया जाता है, न कि केवल बाधाओं से (अर्थात, संख्या 2 के साथ सह-अभाज्य), और इसी तरह समायोजित वेतन वृद्धि में गिनती की जाती है ताकि केवल ऐसे गुणक {{mvar|p}} उत्पन्न होते हैं जो उन छोटे अभाज्यों के साथ सह-अभाज्य होते हैं, पहले स्थान पर।<ref name="Runciman">{{Cite journal | doi = 10.1017/S0956796897002670| title = Functional Pearl: Lazy wheel sieves and spirals of primes| journal = Journal of Functional Programming| volume = 7| issue = 2| pages = 219–225| year = 1997| last1 = Runciman | first1 = Colin| s2cid = 2422563| url = http://eprints.whiterose.ac.uk/3784/1/runcimanc1.pdf}}</ref>
एक और परिशोधन प्रारम्भ में केवल विषम संख्याओं को सूचीबद्ध करना है, {{math|(3, 5, ..., ''n'')}}, और की वृद्धि में गिनें {{math|2''p''}} चरण 3 में, इस प्रकार केवल विषम गुणकों को चिह्नित करना {{mvar|p}}. यह वास्तव में मूल एल्गोरिदम में दिखाई देता है।<ref name="horsley" /><ref name="nicomachus1926" />  इसे पहिया गुणनखंड के साथ सामान्यीकृत किया जा सकता है, प्रारंभिक सूची को केवल प्रथम कुछ अभाज्य संख्याओं के सह-अभाज्य से बनाया जाता है, न कि केवल बाधाओं से (अर्थात, संख्या 2 के साथ सह-अभाज्य), और इसी तरह समायोजित वेतन वृद्धि में गिनती की जाती है ताकि केवल ऐसे गुणक {{mvar|p}} उत्पन्न होते हैं जो उन छोटे अभाज्यों के साथ सह-अभाज्य होते हैं, प्रथम स्थान पर।<ref name="Runciman">{{Cite journal | doi = 10.1017/S0956796897002670| title = Functional Pearl: Lazy wheel sieves and spirals of primes| journal = Journal of Functional Programming| volume = 7| issue = 2| pages = 219–225| year = 1997| last1 = Runciman | first1 = Colin| s2cid = 2422563| url = http://eprints.whiterose.ac.uk/3784/1/runcimanc1.pdf}}</ref>




=== उदाहरण ===
=== उदाहरण ===
30 से कम या 30 के बराबर सभी अभाज्य संख्याएँ ज्ञात करने के लिए, निम्नानुसार आगे बढ़ें।
30 से कम या 30 के समान  सभी अभाज्य संख्याएँ ज्ञात करने के लिए, निम्नानुसार आगे बढ़ें।


सबसे पहले, 2 से 30 तक पूर्णांकों की एक सूची तैयार करें:
सबसे प्रथम, 2 से 30 तक पूर्णांकों की एक सूची तैयार करें:


  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30


सूची में पहला नंबर 2 है; 2 की वृद्धि में 2 से गिनकर 2 के बाद सूची में प्रत्येक दूसरी संख्या को पार करें (ये सूची में 2 के सभी गुणक होंगे):
सूची में प्रथम नंबर 2 है; 2 की वृद्धि में 2 से गिनकर 2 के बाद सूची में प्रत्येक दूसरी संख्या को पार करें (ये सूची में 2 के सभी गुणक होंगे):


  2 3 {{gray|<s> 4 </s>}} 5 {{gray|<s> 6 </s>}} 7 {{gray|<s> 8 </s>}} 9 {{gray|<s>10</s>}} 11 {{gray|<s>12</s>}} 13 {{gray|<s>14</s>}} 15 {{gray|<s>16</s>}} 17 {{gray|<s>18</s>}} 19 {{gray|<s>20</s>}} 21 {{gray|<s>22</s>}} 23 {{gray|<s>24</s>}} 25 {{gray|<s>26</s>}} 27 {{gray|<s>28</s>}} 29 {{gray|<s>30</s>}}
  2 3 {{gray|<s> 4 </s>}} 5 {{gray|<s> 6 </s>}} 7 {{gray|<s> 8 </s>}} 9 {{gray|<s>10</s>}} 11 {{gray|<s>12</s>}} 13 {{gray|<s>14</s>}} 15 {{gray|<s>16</s>}} 17 {{gray|<s>18</s>}} 19 {{gray|<s>20</s>}} 21 {{gray|<s>22</s>}} 23 {{gray|<s>24</s>}} 25 {{gray|<s>26</s>}} 27 {{gray|<s>28</s>}} 29 {{gray|<s>30</s>}}
Line 47: Line 47:
  2 3 {{gray|<s> 4 </s>}} 5 {{gray|<s> 6 </s>}} 7 {{gray|<s> 8 </s>}}{{gray|<s> 9 </s>}}{{gray|<s>10</s>}} 11 {{gray|<s>12</s>}} 13 {{gray|<s>14 </s>}}{{gray|<s>15 </s>}}{{gray|<s>16</s>}} 17 {{gray|<s>18</s>}} 19 {{gray|<s>20 </s>}}{{gray|<s>21 </s>}}{{gray|<s>22</s>}} 23 {{gray|<s>24 </s>}}{{gray|<s>25 </s>}}{{gray|<s>26 </s>}}{{gray|<s>27 </s>}}{{gray|<s>28</s>}} 29 {{gray|<s>30</s>}}
  2 3 {{gray|<s> 4 </s>}} 5 {{gray|<s> 6 </s>}} 7 {{gray|<s> 8 </s>}}{{gray|<s> 9 </s>}}{{gray|<s>10</s>}} 11 {{gray|<s>12</s>}} 13 {{gray|<s>14 </s>}}{{gray|<s>15 </s>}}{{gray|<s>16</s>}} 17 {{gray|<s>18</s>}} 19 {{gray|<s>20 </s>}}{{gray|<s>21 </s>}}{{gray|<s>22</s>}} 23 {{gray|<s>24 </s>}}{{gray|<s>25 </s>}}{{gray|<s>26 </s>}}{{gray|<s>27 </s>}}{{gray|<s>28</s>}} 29 {{gray|<s>30</s>}}


5 के बाद सूची में अगली संख्या 7 है जिसे अभी तक नहीं काटा गया है; अगला कदम 7 के बाद सूची में प्रत्येक 7वीं संख्या को पार करना होगा, लेकिन वे सभी इस बिंदु पर पहले ही पार कर चुके हैं, क्योंकि ये संख्याएं (14, 21, 28) भी छोटी अभाज्य संख्याओं के गुणक हैं क्योंकि 7 × 7 बड़ा है 30 से अधिक। सूची में इस बिंदु पर जिन संख्याओं को नहीं काटा गया है, वे सभी 30 से नीचे की अभाज्य संख्याएँ हैं:
5 के बाद सूची में अगली संख्या 7 है जिसे अभी तक नहीं काटा गया है; अगला कदम 7 के बाद सूची में प्रत्येक 7वीं संख्या को पार करना होगा, लेकिन वे सभी इस बिंदु पर प्रथम ही पार कर चुके हैं, क्योंकि ये संख्याएं (14, 21, 28) भी छोटी अभाज्य संख्याओं के गुणक हैं क्योंकि 7 × 7 बड़ा है 30 से अधिक। सूची में इस बिंदु पर जिन संख्याओं को नहीं काटा गया है, वे सभी 30 से नीचे की अभाज्य संख्याएँ हैं:


  2 3 5 7 11 13 17 19 23 29
  2 3 5 7 11 13 17 19 23 29
Line 72: Line 72:
     'वापसी' सभी मैं ऐसा करता हूं कि ए [i] 'है' 'सत्य'।
     'वापसी' सभी मैं ऐसा करता हूं कि ए [i] 'है' 'सत्य'।


यह एल्गोरिद्म इससे अधिक नहीं सभी अभाज्य संख्याएँ उत्पन्न करता है {{mvar|n}}. इसमें एक सामान्य अनुकूलन शामिल है, जो प्रत्येक अभाज्य के गुणकों की गणना करना शुरू करना है {{mvar|i}} से {{math|''i''<sup>2</sup>}}. इस एल्गोरिथम की [[समय जटिलता]] है {{math|''O''(''n'' log log ''n'')}},{{r|intro}} बशर्ते सरणी अद्यतन एक है {{math|''O''(1)}} ऑपरेशन, जैसा कि आमतौर पर होता है।
यह एल्गोरिद्म इससे अधिक नहीं सभी अभाज्य संख्याएँ उत्पन्न करता है {{mvar|n}}. इसमें एक सामान्य अनुकूलन शामिल है, जो प्रत्येक अभाज्य के गुणकों की गणना करना प्रारम्भ करना है {{mvar|i}} से {{math|''i''<sup>2</sup>}}. इस एल्गोरिथम की [[समय जटिलता]] है {{math|''O''(''n'' log log ''n'')}},{{r|intro}} बशर्ते सरणी अद्यतन एक है {{math|''O''(1)}} ऑपरेशन, जैसा कि आमतौर पर होता है।


=== खंडित छलनी ===
=== खंडित छलनी ===
Line 79: Line 79:
इन समस्याओं का समाधान खंडित छलनी द्वारा प्रस्तुत किया जाता है, जहां एक समय में सीमा के केवल कुछ हिस्सों को छलनी किया जाता है।<ref>Crandall & Pomerance, ''Prime Numbers: A Computational Perspective'', second edition, Springer: 2005, pp. 121–24.</ref> ये 1970 के दशक से जाने जाते हैं, और निम्नानुसार काम करते हैं:{{r|intro}}<ref>{{Cite journal | last1 = Bays | first1 = Carter | last2 = Hudson | first2 = Richard H. | year = 1977 | title = The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10<sup>12</sup> | journal = BIT | volume = 17 | issue = 2 | pages = 121–127 | doi = 10.1007/BF01932283 | s2cid = 122592488 }}</ref>
इन समस्याओं का समाधान खंडित छलनी द्वारा प्रस्तुत किया जाता है, जहां एक समय में सीमा के केवल कुछ हिस्सों को छलनी किया जाता है।<ref>Crandall & Pomerance, ''Prime Numbers: A Computational Perspective'', second edition, Springer: 2005, pp. 121–24.</ref> ये 1970 के दशक से जाने जाते हैं, और निम्नानुसार काम करते हैं:{{r|intro}}<ref>{{Cite journal | last1 = Bays | first1 = Carter | last2 = Hudson | first2 = Richard H. | year = 1977 | title = The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10<sup>12</sup> | journal = BIT | volume = 17 | issue = 2 | pages = 121–127 | doi = 10.1007/BF01932283 | s2cid = 122592488 }}</ref>
# श्रेणी को 2 से विभाजित करें {{mvar|n}} कुछ आकार के खंडों में {{math|Δ ≤ {{sqrt|''n''}}}}.
# श्रेणी को 2 से विभाजित करें {{mvar|n}} कुछ आकार के खंडों में {{math|Δ ≤ {{sqrt|''n''}}}}.
# नियमित छलनी का उपयोग करके पहले (यानी सबसे कम) खंड में अभाज्य संख्याएँ खोजें।
# नियमित छलनी का उपयोग करके प्रथम (यानी सबसे कम) खंड में अभाज्य संख्याएँ खोजें।
# निम्न में से प्रत्येक खंड के लिए, बढ़ते क्रम में, के साथ {{mvar|m}} खंड का सर्वोच्च मान होने के कारण, इसमें अभाज्य संख्याएँ इस प्रकार खोजें:
# निम्न में से प्रत्येक खंड के लिए, बढ़ते क्रम में, के साथ {{mvar|m}} खंड का सर्वोच्च मान होने के कारण, इसमें अभाज्य संख्याएँ इस प्रकार खोजें:
## आकार की एक बूलियन सरणी सेट करें {{math|Δ}}.
## आकार की एक बूलियन सरणी सेट करें {{math|Δ}}.
## प्रत्येक प्राइम के गुणकों के अनुरूप सरणी में पदों को गैर-प्राइम के रूप में चिह्नित करें {{math|''p'' ≤ {{sqrt|''m''}}}} के चरणों में इसके गुणकों की गणना करके अब तक पाया गया {{math|''p''}} के निम्नतम गुणज से शुरू करते हुए {{math|''p''}} बीच में {{math|{{mvar|m}} - Δ}} और {{mvar|m}}.
## प्रत्येक प्राइम के गुणकों के अनुरूप सरणी में पदों को गैर-प्राइम के रूप में चिह्नित करें {{math|''p'' ≤ {{sqrt|''m''}}}} के चरणों में इसके गुणकों की गणना करके अब तक पाया गया {{math|''p''}} के निम्नतम गुणज से प्रारम्भ करते हुए {{math|''p''}} बीच में {{math|{{mvar|m}} - Δ}} और {{mvar|m}}.
## सरणी में शेष गैर-चिह्नित स्थान खंड में primes के अनुरूप हैं। इन अभाज्य संख्याओं के किसी गुणज को चिन्हित करना आवश्यक नहीं है, क्योंकि ये सभी अभाज्य संख्याएँ इससे बड़ी हैं {{math|{{sqrt|''m''}}}}, से संबंधित {{math|''k'' ≥ 1}}, किसी के पास <math>(k\Delta + 1)^2 > (k+1)\Delta</math>.
## सरणी में शेष गैर-चिह्नित स्थान खंड में primes के अनुरूप हैं। इन अभाज्य संख्याओं के किसी गुणज को चिन्हित करना आवश्यक नहीं है, क्योंकि ये सभी अभाज्य संख्याएँ इससे बड़ी हैं {{math|{{sqrt|''m''}}}}, से संबंधित {{math|''k'' ≥ 1}}, किसी के पास <math>(k\Delta + 1)^2 > (k+1)\Delta</math>.


अगर {{math|Δ}} को चुना गया है {{math|{{sqrt|''n''}}}}, एल्गोरिथम की अंतरिक्ष जटिलता है {{math|''O''({{sqrt|''n''}})}}, जबकि समय की जटिलता नियमित छलनी के समान है।{{r|intro}}
अगर {{math|Δ}} को चुना गया है {{math|{{sqrt|''n''}}}}, एल्गोरिथम की भिन्नता िक्ष जटिलता है {{math|''O''({{sqrt|''n''}})}}, जबकि समय की जटिलता नियमित छलनी के समान है।{{r|intro}}


ऊपरी सीमा वाली श्रेणियों के लिए {{math|''n''}} इतना बड़ा कि छनाई नीचे की ओर चुभती है {{math|{{sqrt|''n''}}}} एराटोस्थनीज की पृष्ठ खंडित छलनी की आवश्यकता के अनुसार मेमोरी में फिट नहीं हो सकता है, इसके बजाय [[सोरेनसन की छलनी]] की तरह एक धीमी लेकिन अधिक स्थान-कुशल छलनी का उपयोग किया जा सकता है।<ref>J. Sorenson, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.1737 "The pseudosquares prime sieve"], ''Proceedings of the 7th International Symposium on Algorithmic Number Theory''. (ANTS-VII, 2006).</ref>
ऊपरी सीमा वाली श्रेणियों के लिए {{math|''n''}} इतना बड़ा कि छनाई नीचे की ओर चुभती है {{math|{{sqrt|''n''}}}} एराटोस्थनीज की पृष्ठ खंडित छलनी की आवश्यकता के अनुसार मेमोरी में फिट नहीं हो सकता है, इसके अतिरिक्त [[सोरेनसन की छलनी]] की तरह एक धीमी लेकिन अधिक स्थान-कुशल छलनी का उपयोग किया जा सकता है।<ref>J. Sorenson, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.1737 "The pseudosquares prime sieve"], ''Proceedings of the 7th International Symposium on Algorithmic Number Theory''. (ANTS-VII, 2006).</ref>




=== वृद्धिशील छलनी ===
=== वृद्धिशील छलनी ===
छलनी का एक वृद्धिशील सूत्रीकरण<ref name="ONeill">O'Neill, Melissa E., [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], ''Journal of Functional Programming'', published online by Cambridge University Press 9 October 2008 {{doi|10.1017/S0956796808007004}}, pp. 10, 11 (contains two incremental sieves in Haskell: a priority-queue–based one by O'Neill and a list–based, by Richard Bird).</ref> उनके गुणकों की पीढ़ी के साथ प्राइम्स की पीढ़ी को अंतःस्थापित करके अनिश्चित काल तक (यानी, ऊपरी बाउंड के बिना) प्राइम उत्पन्न करता है (ताकि प्राइम को गुणकों के बीच अंतराल में पाया जा सके), जहां प्रत्येक प्राइम के गुणक {{mvar|p}} की वृद्धि में प्राइम के वर्ग से गिनती करके सीधे उत्पन्न होते हैं {{mvar|p}} (या {{math|2''p''}} विषम अभाज्य संख्याओं के लिए)। दक्षता पर प्रतिकूल प्रभाव से बचने के लिए, पीढ़ी को केवल तभी शुरू किया जाना चाहिए जब प्राइम का वर्ग पहुंच गया हो। इसे [[डेटाफ्लो प्रोग्रामिंग]] प्रतिमान के तहत प्रतीकात्मक रूप से व्यक्त किया जा सकता है
छलनी का एक वृद्धिशील सूत्रीकरण<ref name="ONeill">O'Neill, Melissa E., [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf "The Genuine Sieve of Eratosthenes"], ''Journal of Functional Programming'', published online by Cambridge University Press 9 October 2008 {{doi|10.1017/S0956796808007004}}, pp. 10, 11 (contains two incremental sieves in Haskell: a priority-queue–based one by O'Neill and a list–based, by Richard Bird).</ref> उनके गुणकों की पीढ़ी के साथ प्राइम्स की पीढ़ी को अंतःस्थापित करके अनिश्चित काल तक (यानी, ऊपरी बाउंड के बिना) प्राइम उत्पन्न करता है (ताकि प्राइम को गुणकों के बीच भिन्नता ाल में पाया जा सके), जहां प्रत्येक प्राइम के गुणक {{mvar|p}} की वृद्धि में प्राइम के वर्ग से गिनती करके सीधे उत्पन्न होते हैं {{mvar|p}} (या {{math|2''p''}} विषम अभाज्य संख्याओं के लिए)। दक्षता पर प्रतिकूल प्रभाव से बचने के लिए, पीढ़ी को केवल तभी प्रारम्भ किया जाना चाहिए जब प्राइम का वर्ग पहुंच गया हो। इसे [[डेटाफ्लो प्रोग्रामिंग]] प्रतिमान के तहत प्रतीकात्मक रूप से व्यक्त किया जा सकता है


  primes = [2, 3, ...] \ p², p²+p, ...] for p in primes],
  primes = [2, 3, ...] \ p², p²+p, ...] for p in primes],
Line 97: Line 97:
साथ सूची बोध संकेतन का उपयोग करना <code>\</code> पूरक (सेट सिद्धांत) # संख्याओं की [[अंकगणितीय प्रगति]] के सापेक्ष पूरक को दर्शाते हुए।
साथ सूची बोध संकेतन का उपयोग करना <code>\</code> पूरक (सेट सिद्धांत) # संख्याओं की [[अंकगणितीय प्रगति]] के सापेक्ष पूरक को दर्शाते हुए।


एक समय में एक प्राइम अनुक्रमिक प्राइम्स द्वारा ट्रायल डिवीजन के माध्यम से कंपोजिट को पुनरावृत्त रूप से छलनी करके भी प्राइम्स का उत्पादन किया जा सकता है। यह एराटोस्थनीज की छलनी नहीं है, लेकिन अक्सर इसके साथ भ्रमित होता है, भले ही एराटोस्थनीज की छलनी उनके लिए परीक्षण के बजाय सीधे कंपोजिट उत्पन्न करती है। ट्रायल डिवीजन में प्राइम्स की रेंज उत्पन्न करने में एराटोस्थनीज की छलनी की तुलना में एल्गोरिदम का बदतर सैद्धांतिक विश्लेषण है।<ref name="ONeill"/>
एक समय में एक प्राइम अनुक्रमिक प्राइम्स द्वारा ट्रायल डिवीजन के माध्यम से कंपोजिट को पुनरावृत्त रूप से छलनी करके भी प्राइम्स का उत्पादन किया जा सकता है। यह एराटोस्थनीज की छलनी नहीं है, लेकिन अक्सर इसके साथ भ्रमित होता है, भले ही एराटोस्थनीज की छलनी उनके लिए परीक्षण के अतिरिक्त सीधे कंपोजिट उत्पन्न करती है। ट्रायल डिवीजन में प्राइम्स की रेंज उत्पन्न करने में एराटोस्थनीज की छलनी की तुलना में एल्गोरिदम का बदतर सैद्धांतिक विश्लेषण है।<ref name="ONeill"/>


प्रत्येक अभाज्य का परीक्षण करते समय, इष्टतम परीक्षण प्रभाग एल्गोरिथ्म सभी अभाज्य संख्याओं का उपयोग करता है जो इसके वर्गमूल से अधिक नहीं होती हैं, जबकि एराटोस्थनीज की छलनी प्रत्येक सम्मिश्र को केवल इसके प्रमुख कारकों से उत्पन्न करती है, और सम्मिश्रों के बीच मुफ्त में अभाज्य प्राप्त करती है। [[डेविड टर्नर (कंप्यूटर वैज्ञानिक)]] द्वारा व्यापक रूप से ज्ञात 1975 [[कार्यात्मक प्रोग्रामिंग]] चलनी कोड<ref>Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (<syntaxhighlight lang="haskell" inline>primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0</syntaxhighlight>). But see also [http://dl.acm.org/citation.cfm?id=811543&dl=ACM&coll=DL&CFID=663592028&CFTOKEN=36641676 Peter Henderson, Morris, James Jr., A Lazy Evaluator, 1976], where we [http://www.seas.gwu.edu/~rhyspj/cs3221/lab8/henderson.pdf find the following], attributed to P. Quarendon: <syntaxhighlight lang="python" inline>primeswrt[x;l] = if car[l] mod x=0 then primeswrt[x;cdr[l]] else cons[car[l];primeswrt[x;cdr[l]]] ; primes[l] = cons[car[l];primes[primeswrt[car[l];cdr[l]]]] ; primes[integers[2]]</syntaxhighlight>; the priority is unclear.</ref> अक्सर एराटोस्थनीज की छलनी के उदाहरण के रूप में प्रस्तुत किया जाता है<ref name="Runciman"/>लेकिन वास्तव में एक उप-इष्टतम परीक्षण प्रभाग छलनी है।<ref name="ONeill"/>
प्रत्येक अभाज्य का परीक्षण करते समय, इष्टतम परीक्षण प्रभाग एल्गोरिथ्म सभी अभाज्य संख्याओं का उपयोग करता है जो इसके वर्गमूल से अधिक नहीं होती हैं, जबकि एराटोस्थनीज की छलनी प्रत्येक सम्मिश्र को केवल इसके प्रमुख कारकों से उत्पन्न करती है, और सम्मिश्रों के बीच मुफ्त में अभाज्य प्राप्त करती है। [[डेविड टर्नर (कंप्यूटर वैज्ञानिक)]] द्वारा व्यापक रूप से ज्ञात 1975 [[कार्यात्मक प्रोग्रामिंग]] चलनी कोड<ref>Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (<syntaxhighlight lang="haskell" inline>primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0</syntaxhighlight>). But see also [http://dl.acm.org/citation.cfm?id=811543&dl=ACM&coll=DL&CFID=663592028&CFTOKEN=36641676 Peter Henderson, Morris, James Jr., A Lazy Evaluator, 1976], where we [http://www.seas.gwu.edu/~rhyspj/cs3221/lab8/henderson.pdf find the following], attributed to P. Quarendon: <syntaxhighlight lang="python" inline>primeswrt[x;l] = if car[l] mod x=0 then primeswrt[x;cdr[l]] else cons[car[l];primeswrt[x;cdr[l]]] ; primes[l] = cons[car[l];primes[primeswrt[car[l];cdr[l]]]] ; primes[integers[2]]</syntaxhighlight>; the priority is unclear.</ref> अक्सर एराटोस्थनीज की छलनी के उदाहरण के रूप में प्रस्तुत किया जाता है<ref name="Runciman"/>लेकिन वास्तव में एक उप-इष्टतम परीक्षण प्रभाग छलनी है।<ref name="ONeill"/>
Line 103: Line 103:


== एल्गोरिथम जटिलता ==
== एल्गोरिथम जटिलता ==
एराटोस्थनीज की छलनी कंप्यूटर के प्रदर्शन को बेंचमार्क करने का एक लोकप्रिय तरीका है।<ref name="peng1985fall">{{cite news | url=https://archive.org/stream/byte-magazine-1985-11/1985_11_BYTE_10-11_Inside_the_IBM_PCs#page/n245/mode/2up | title=चलनी के माध्यम से एक मिलियन प्राइम्स| work=BYTE | date=Fall 1985 | access-date=19 March 2016 | author=Peng, T. A. | pages=243–244}}</ref> नीचे सभी अभाज्य संख्याओं की गणना करने की समय जटिलता {{mvar|n}} [[रैंडम एक्सेस मशीन]] मॉडल में है {{math|''O''(''n'' log log ''n'')}} संचालन, इस तथ्य का प्रत्यक्ष परिणाम है कि प्रमुख हार्मोनिक श्रृंखला स्पर्शोन्मुख रूप से पहुंचती है {{math|log log ''n''}}. इसमें इनपुट आकार के संबंध में एक घातीय समय जटिलता है, हालांकि, जो इसे छद्म-बहुपद समय | छद्म-बहुपद एल्गोरिदम बनाता है। बुनियादी एल्गोरिदम की आवश्यकता है {{math|''O''(''n'')}} स्मृति का।
एराटोस्थनीज की छलनी कंप्यूटर के प्रदर्शन को बेंचमार्क करने का एक लोकप्रिय तरीका है।<ref name="peng1985fall">{{cite news | url=https://archive.org/stream/byte-magazine-1985-11/1985_11_BYTE_10-11_Inside_the_IBM_PCs#page/n245/mode/2up | title=चलनी के माध्यम से एक मिलियन प्राइम्स| work=BYTE | date=Fall 1985 | access-date=19 March 2016 | author=Peng, T. A. | pages=243–244}}</ref> नीचे सभी अभाज्य संख्याओं की गणना करने की समय जटिलता {{mvar|n}} [[रैंडम एक्सेस मशीन]] मॉडल में है {{math|''O''(''n'' log log ''n'')}} संचालन, इस तथ्य का प्रत्यक्ष परिणाम है कि प्रमुख हार्मोनिक श्रृंखला स्पर्शोन्मुख रूप से पहुंचती है {{math|log log ''n''}}. इसमें इनपुट आकार के संबंध में एक घातीय समय जटिलता है, चूँकि, जो इसे छद्म-बहुपद समय | छद्म-बहुपद एल्गोरिदम बनाता है। बुनियादी एल्गोरिदम की आवश्यकता है {{math|''O''(''n'')}} स्मृति का।


एल्गोरिदम की [[थोड़ी जटिलता]] है {{math|''O''<big>(</big>''n'' (log ''n'') (log log ''n'')<big>)</big>}} बिट ऑपरेशंस की मेमोरी आवश्यकता के साथ {{math|''O''(''n'')}}.<ref>Pritchard, Paul, "Linear prime-number sieves: a family tree," ''Sci. Comput. Programming'' '''9''':1 (1987), pp. 17–35.</ref>
एल्गोरिदम की [[थोड़ी जटिलता]] है {{math|''O''<big>(</big>''n'' (log ''n'') (log log ''n'')<big>)</big>}} बिट ऑपरेशंस की मेमोरी आवश्यकता के साथ {{math|''O''(''n'')}}.<ref>Pritchard, Paul, "Linear prime-number sieves: a family tree," ''Sci. Comput. Programming'' '''9''':1 (1987), pp. 17–35.</ref>
सामान्य रूप से लागू किए गए पृष्ठ खंडित संस्करण में समान परिचालन जटिलता होती है {{math|''O''(''n'' log log ''n'')}} गैर-खंडित संस्करण के रूप में लेकिन अंतरिक्ष आवश्यकताओं को खंड पृष्ठ के बहुत न्यूनतम आकार तक कम कर देता है और साथ ही आकार के क्रमिक पृष्ठ खंडों से कंपोजिट को कम करने के लिए उपयोग की जाने वाली श्रेणी के वर्गमूल से कम आधार प्राइम्स को स्टोर करने के लिए आवश्यक मेमोरी {{math|''O''<big><big>(</big></big>{{sfrac|{{sqrt|''n''}}|log ''n''}}<big><big>)</big></big>}}.
सामान्य रूप से लागू किए गए पृष्ठ खंडित संस्करण में समान परिचालन जटिलता होती है {{math|''O''(''n'' log log ''n'')}} गैर-खंडित संस्करण के रूप में लेकिन भिन्नता िक्ष आवश्यकताओं को खंड पृष्ठ के बहुत न्यूनतम आकार तक कम कर देता है और साथ ही आकार के क्रमिक पृष्ठ खंडों से कंपोजिट को कम करने के लिए उपयोग की जाने वाली श्रेणी के वर्गमूल से कम आधार प्राइम्स को स्टोर करने के लिए आवश्यक मेमोरी {{math|''O''<big><big>(</big></big>{{sfrac|{{sqrt|''n''}}|log ''n''}}<big><big>)</big></big>}}.


एराटोस्थनीज की छलनी का एक विशेष (शायद ही कभी, यदि कभी, लागू किया गया) खंडित संस्करण, बुनियादी अनुकूलन के साथ, उपयोग करता है {{math|''O''(''n'')}} संचालन और {{math|''O''<big><big>(</big></big>{{sqrt|''n''}}{{sfrac|log log ''n''|log ''n''}}<big><big>)</big></big>}} स्मृति के टुकड़े।<ref name="Pritchard1">Paul Pritchard, "A sublinear additive sieve for finding prime numbers", ''Communications of the ACM'' 24 (1981), 18–23. {{MR|600730}}</ref><ref name="Pritchard2">Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. {{MR|685983}}</ref><ref name="Pritchard3">Paul Pritchard, "Fast compact prime number sieves" (among others), ''Journal of Algorithms'' 4
एराटोस्थनीज की छलनी का एक विशेष (शायद ही कभी, यदि कभी, लागू किया गया) खंडित संस्करण, बुनियादी अनुकूलन के साथ, उपयोग करता है {{math|''O''(''n'')}} संचालन और {{math|''O''<big><big>(</big></big>{{sqrt|''n''}}{{sfrac|log log ''n''|log ''n''}}<big><big>)</big></big>}} स्मृति के टुकड़े।<ref name="Pritchard1">Paul Pritchard, "A sublinear additive sieve for finding prime numbers", ''Communications of the ACM'' 24 (1981), 18–23. {{MR|600730}}</ref><ref name="Pritchard2">Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. {{MR|685983}}</ref><ref name="Pritchard3">Paul Pritchard, "Fast compact prime number sieves" (among others), ''Journal of Algorithms'' 4
(1983), 332–344. {{MR|729229}}</ref>
(1983), 332–344. {{MR|729229}}</ref>
[[बिग ओ नोटेशन]] का उपयोग करने से स्थिर कारकों और ऑफ़सेट की अनदेखी होती है जो व्यावहारिक श्रेणियों के लिए बहुत महत्वपूर्ण हो सकते हैं: एराटोस्थनीज भिन्नता की छलनी जिसे प्रिटचर्ड व्हील सीव के रूप में जाना जाता है<ref name="Pritchard1" /><ref name="Pritchard2" /><ref name="Pritchard3" />एक है {{math|''O''(''n'')}} प्रदर्शन, लेकिन इसके बुनियादी कार्यान्वयन के लिए या तो एक बड़ी सरणी एल्गोरिदम की आवश्यकता होती है जो इसकी प्रयोग करने योग्य सीमा को उपलब्ध स्मृति की मात्रा तक सीमित करती है अन्यथा स्मृति उपयोग को कम करने के लिए इसे पृष्ठ खंडित करने की आवश्यकता होती है। स्मृति को बचाने के लिए पेज सेगमेंटेशन के साथ कार्यान्वित किए जाने पर, मूल एल्गोरिदम को अभी भी आवश्यकता होती है {{math|''O''<big><big>(</big></big>{{sfrac|''n''|log ''n''}}<big><big>)</big></big>}} मेमोरी के बिट्स (एराटोस्थनीज के मूल पृष्ठ खंडित छलनी की आवश्यकता से बहुत अधिक {{math|''O''<big><big>(</big></big>{{sfrac|{{sqrt|''n''}}|log ''n''}}<big><big>)</big></big>}} स्मृति के टुकड़े)। प्रिटचर्ड के काम ने एक बड़े स्थिर कारक की कीमत पर स्मृति की आवश्यकता को कम कर दिया। हालांकि परिणामी पहिया छलनी है {{math|''O''(''n'')}} प्रदर्शन और एक स्वीकार्य स्मृति आवश्यकता, यह व्यावहारिक रूप से छानने की सीमा के लिए एराटोस्थनीज की यथोचित व्हील फैक्टराइज़्ड बुनियादी छलनी से तेज़ नहीं है।
[[बिग ओ नोटेशन]] का उपयोग करने से स्थिर कारकों और ऑफ़सेट की अनदेखी होती है जो व्यावहारिक श्रेणियों के लिए बहुत महत्वपूर्ण हो सकते हैं: एराटोस्थनीज भिन्नता की छलनी जिसे प्रिटचर्ड व्हील सीव के रूप में जाना जाता है<ref name="Pritchard1" /><ref name="Pritchard2" /><ref name="Pritchard3" />एक है {{math|''O''(''n'')}} प्रदर्शन, लेकिन इसके बुनियादी कार्यान्वयन के लिए या तो एक बड़ी सरणी एल्गोरिदम की आवश्यकता होती है जो इसकी प्रयोग करने योग्य सीमा को उपलब्ध स्मृति की मात्रा तक सीमित करती है अन्यथा स्मृति उपयोग को कम करने के लिए इसे पृष्ठ खंडित करने की आवश्यकता होती है। स्मृति को बचाने के लिए पेज सेगमेंटेशन के साथ कार्यान्वित किए जाने पर, मूल एल्गोरिदम को अभी भी आवश्यकता होती है {{math|''O''<big><big>(</big></big>{{sfrac|''n''|log ''n''}}<big><big>)</big></big>}} मेमोरी के बिट्स (एराटोस्थनीज के मूल पृष्ठ खंडित छलनी की आवश्यकता से बहुत अधिक {{math|''O''<big><big>(</big></big>{{sfrac|{{sqrt|''n''}}|log ''n''}}<big><big>)</big></big>}} स्मृति के टुकड़े)। प्रिटचर्ड के काम ने एक बड़े स्थिर कारक की कीमत पर स्मृति की आवश्यकता को कम कर दिया। चूँकि परिणामी पहिया छलनी है {{math|''O''(''n'')}} प्रदर्शन और एक स्वीकार्य स्मृति आवश्यकता, यह व्यावहारिक रूप से छानने की सीमा के लिए एराटोस्थनीज की यथोचित व्हील फैक्टराइज़्ड बुनियादी छलनी से तेज़ नहीं है।


== यूलर की छलनी ==
== यूलर की छलनी ==
Line 124: Line 124:
  | volume = 21| hdl = 1813/6407 | s2cid = 11990373 | url = https://ecommons.cornell.edu/bitstream/1813/6407/1/77-313.pdf
  | volume = 21| hdl = 1813/6407 | s2cid = 11990373 | url = https://ecommons.cornell.edu/bitstream/1813/6407/1/77-313.pdf
  | hdl-access = free
  | hdl-access = free
  }}.</ref> यह भी, 2 से लेकर संख्याओं की [[सूची (कंप्यूटिंग)]] के साथ शुरू होता है {{mvar|n}} क्रम में। प्रत्येक चरण पर पहले तत्व को अगले अभाज्य के रूप में पहचाना जाता है, सूची के प्रत्येक तत्व से गुणा किया जाता है (इस प्रकार स्वयं से शुरू होता है), और परिणाम बाद में हटाने के लिए सूची में चिह्नित किए जाते हैं। प्रारंभिक तत्व और चिह्नित तत्वों को कार्य क्रम से हटा दिया जाता है, और प्रक्रिया दोहराई जाती है:
  }}.</ref> यह भी, 2 से लेकर संख्याओं की [[सूची (कंप्यूटिंग)]] के साथ प्रारम्भ होता है {{mvar|n}} क्रम में। प्रत्येक चरण पर प्रथम तत्व को अगले अभाज्य के रूप में पहचाना जाता है, सूची के प्रत्येक तत्व से गुणा किया जाता है (इस प्रकार स्वयं से प्रारम्भ होता है), और परिणाम बाद में हटाने के लिए सूची में चिह्नित किए जाते हैं। प्रारंभिक तत्व और चिह्नित तत्वों को कार्य क्रम से हटा दिया जाता है, और प्रक्रिया दोहराई जाती है:
<div शैली = फ़ॉन्ट-आकार: 85%; >   
<div शैली = फ़ॉन्ट-आकार: 85%; >   
[2] (3) 5 7 <यू>9</यू> 11 13 <यू>15</यू> 17 19 <यू>21</यू> 23 25 <यू>27</यू> 29 31 <यू >33 35 37 <u>39</u> 41 43 <u>45</u> 47 49 <u>51</u> 53 55 <u>57</u> 59 61 <u >63</u> 65 67 <u>69</u> 71 73 <u>75</u> 77 79 ...
[2] (3) 5 7 <यू>9</यू> 11 13 <यू>15</यू> 17 19 <यू>21</यू> 23 25 <यू>27</यू> 29 31 <यू >33 35 37 <u>39</u> 41 43 <u>45</u> 47 49 <u>51</u> 53 55 <u>57</u> 59 61 <u >63</u> 65 67 <u>69</u> 71 73 <u>75</u> 77 79 ...
Line 133: Line 133:
</div>
</div>


यहाँ उदाहरण को एल्गोरिथम के पहले चरण के बाद ऑड्स से शुरू करते हुए दिखाया गया है। इस प्रकार, पर {{mvar|k}}वाँ चरण के सभी शेष गुणज {{mvar|k}}वें अभाज्य को सूची से हटा दिया जाता है, जिसमें बाद में पहले के साथ केवल सहअभाज्य संख्याएँ होंगी {{mvar|k}} primes (cf. Wheel factorization), ताकि सूची अगले अभाज्य से शुरू हो, और इसके पहले तत्व के वर्ग के नीचे की सभी संख्याएँ भी अभाज्य होंगी।
यहाँ उदाहरण को एल्गोरिथम के प्रथम चरण के बाद ऑड्स से प्रारम्भ करते हुए दिखाया गया है। इस प्रकार, पर {{mvar|k}}वाँ चरण के सभी शेष गुणज {{mvar|k}}वें अभाज्य को सूची से हटा दिया जाता है, जिसमें बाद में प्रथम के साथ केवल सहअभाज्य संख्याएँ होंगी {{mvar|k}} primes (cf. Wheel factorization), ताकि सूची अगले अभाज्य से प्रारम्भ हो, और इसके प्रथम तत्व के वर्ग के नीचे की सभी संख्याएँ भी अभाज्य होंगी।


इस प्रकार, अभाज्य संख्याओं का एक बंधा हुआ अनुक्रम उत्पन्न करते समय, जब अगली पहचानी गई अभाज्य ऊपरी सीमा के वर्गमूल से अधिक हो जाती है, तो सूची में शेष सभी संख्याएँ अभाज्य होती हैं।<ref name="intro" />ऊपर दिए गए उदाहरण में 11 को अगले अभाज्य के रूप में पहचानने पर, 80 से कम या उसके बराबर सभी अभाज्य संख्याओं की सूची देकर प्राप्त किया जाता है।
इस प्रकार, अभाज्य संख्याओं का एक बंधा हुआ अनुक्रम उत्पन्न करते समय, जब अगली पहचानी गई अभाज्य ऊपरी सीमा के वर्गमूल से अधिक हो जाती है, तो सूची में शेष सभी संख्याएँ अभाज्य होती हैं।<ref name="intro" />ऊपर दिए गए उदाहरण में 11 को अगले अभाज्य के रूप में पहचानने पर, 80 से कम या उसके समान  सभी अभाज्य संख्याओं की सूची देकर प्राप्त किया जाता है।


ध्यान दें कि किसी चरण द्वारा छोड़ी जाने वाली संख्याएँ अभी भी उस चरण में गुणकों को चिह्नित करते समय उपयोग की जाती हैं, उदाहरण के लिए, 3 के गुणकों के लिए यह है {{nowrap|1=3 × 3 = 9}}, {{nowrap|1=3 × 5 = 15}}, {{nowrap|1=3 × 7 = 21}}, {{nowrap|1=3 × '''''9''''' = 27}}, ..., {{nowrap|1=3 × '''''15''''' = 45}}, ..., इसलिए इससे निपटने में सावधानी बरतनी चाहिए।<ref name="intro" />
ध्यान दें कि किसी चरण द्वारा छोड़ी जाने वाली संख्याएँ अभी भी उस चरण में गुणकों को चिह्नित करते समय उपयोग की जाती हैं, उदाहरण के लिए, 3 के गुणकों के लिए यह है {{nowrap|1=3 × 3 = 9}}, {{nowrap|1=3 × 5 = 15}}, {{nowrap|1=3 × 7 = 21}}, {{nowrap|1=3 × '''''9''''' = 27}}, ..., {{nowrap|1=3 × '''''15''''' = 45}}, ..., इसलिए इससे निपटने में सावधानी बरतनी चाहिए।<ref name="intro" />

Revision as of 08:42, 10 June 2023

For the sculpture, see The Sieve of Eratosthenes (sculpture).
एराटोस्थनीज की छलनी: 121 से नीचे के अभाज्यों के लिए एल्गोरिथम चरण (प्राइम के वर्ग से प्रारम्भ करने के अनुकूलन सहित)।

गणित में, एराटोस्थनीज की छलनी किसी भी सीमा तक सभी अभाज्य संख्याओं को की शोध के लिए प्राचीन कलन विधि है।

यह पुनरावृत्त रूप से समग्र संख्या (अर्थात, अभाज्य नहीं) के रूप में चिह्नित करता है, प्रत्येक अभाज्य संख्या के गुणकों को, प्रथम अभाज्य संख्या 2 के साथ प्रारम्भ करता है, । किसी दिए गए अभाज्य के गुणकों को अंकगणित के साथ उस अभाज्य से प्रारम्भ होने वाली संख्याओं के अनुक्रम के रूप में उत्पन्न किया जाता है। प्रगति जो उस प्रधान के समान है।[1] प्रत्येक अभाज्य द्वारा विभाज्यता के लिए प्रत्येक उम्मीदवार संख्या का क्रमिक रूप से परीक्षण करने के लिए परीक्षण प्रभाग का उपयोग करने से छलनी महत्वपूर्ण है।[2] प्रत्येक अनुशोधित प्राइम के सभी गुणकों को कंपोजिट के रूप में चिह्नित किया गया है, शेष अचिह्नित संख्याएं प्राइम हैं।

छलनी का सबसे प्रथम ज्ञात संदर्भ (Ancient Greek: κόσκινον Ἐρατοσθένους, कोस्किनॉन एराटोस्थेनस) अंकगणित के निकोमाचस के परिचय में,[3] प्रारंभिक 2 सेंट है। CE पुस्तक जो इसका श्रेय एराटोस्थनीज को देती है, जो कि तीसरा प्रतिशत है। बीसीई ग्रीक गणित, चूँकि अभाज्य संख्याओं के अतिरिक्त विषम संख्याओं द्वारा छलनी का वर्णन करता है।[4] कई जनरेटिंग प्राइम्स में से प्राइम सीवेस, यह सभी छोटे प्राइम्स की शोध के सबसे कुशल उपाय है। इसका उपयोग अंकगणितीय प्रगति में अभाज्य संख्या की अनुशोधन के लिए किया जा सकता है।[5]


सिंहावलोकन

Sift the Two's and Sift the Three's:
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

Anonymous[6]

एक अभाज्य संख्या एक प्राकृतिक संख्या है जिसमें दो अलग-अलग प्राकृतिक संख्या विभाजक होते हैं: संख्या 1 और स्वयं।

किसी दिए गए पूर्णांक से कम या उसके समान सभी अभाज्य संख्याएँ ज्ञात करना n एराटोस्थनीज की विधि द्वारा:

  1. 2 से लगातार पूर्णांकों की सूची बनाएं n: (2, 3, 4, ..., n).
  2. प्रारम्भ में, चलो p समान 2, सबसे छोटी अभाज्य संख्या।
  3. के गुणजों की गणना करें p की वृद्धि में गिनती करके p से 2p को n, और उन्हें सूची में चिह्नित करें (ये होंगे 2p, 3p, 4p, ...; p खुद को चिह्नित नहीं किया जाना चाहिए)।
  4. सूची में सबसे छोटी संख्या का पता लगाएं p जो चिह्नित नहीं है। अगर ऐसी कोई संख्या नहीं थी, तो रुकें। नहीं तो जाने दो p अब इस नई संख्या के समान करें (जो अगला अभाज्य है), और चरण 3 से दोहराएं।
  5. जब एल्गोरिथम समाप्त हो जाता है, तो सूची में चिह्नित नहीं की गई शेष संख्याएँ नीचे दी गई सभी अभाज्य संख्याएँ होती हैं n.

यहाँ मुख्य विचार यह है कि प्रत्येक मान दिया गया है p प्राइम होगा, क्योंकि अगर यह कंपोजिट होता तो इसे किसी अन्य, छोटे प्राइम के मल्टीपल के रूप में चिह्नित किया जाता। ध्यान दें कि कुछ संख्याओं को एक से अधिक बार चिह्नित किया जा सकता है (उदाहरण के लिए, 15 को 3 और 5 दोनों के लिए चिह्नित किया जाएगा)।

परिशोधन के रूप में, चरण 3 में से प्रारम्भ करके संख्याओं को चिह्नित करना पर्याप्त है p2, के सभी छोटे गुणकों के रूप में p उस बिंदु पर प्रथम ही चिह्नित किया जा चुका होगा। इसका मतलब है कि एल्गोरिदम को चरण 4 में समाप्त करने की अनुमति है जब p2 से बड़ा है n.[1] एक और परिशोधन प्रारम्भ में केवल विषम संख्याओं को सूचीबद्ध करना है, (3, 5, ..., n), और की वृद्धि में गिनें 2p चरण 3 में, इस प्रकार केवल विषम गुणकों को चिह्नित करना p. यह वास्तव में मूल एल्गोरिदम में दिखाई देता है।[1][4] इसे पहिया गुणनखंड के साथ सामान्यीकृत किया जा सकता है, प्रारंभिक सूची को केवल प्रथम कुछ अभाज्य संख्याओं के सह-अभाज्य से बनाया जाता है, न कि केवल बाधाओं से (अर्थात, संख्या 2 के साथ सह-अभाज्य), और इसी तरह समायोजित वेतन वृद्धि में गिनती की जाती है ताकि केवल ऐसे गुणक p उत्पन्न होते हैं जो उन छोटे अभाज्यों के साथ सह-अभाज्य होते हैं, प्रथम स्थान पर।[7]


उदाहरण

30 से कम या 30 के समान सभी अभाज्य संख्याएँ ज्ञात करने के लिए, निम्नानुसार आगे बढ़ें।

सबसे प्रथम, 2 से 30 तक पूर्णांकों की एक सूची तैयार करें: 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

सूची में प्रथम नंबर 2 है; 2 की वृद्धि में 2 से गिनकर 2 के बाद सूची में प्रत्येक दूसरी संख्या को पार करें (ये सूची में 2 के सभी गुणक होंगे): 

2 3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

सूची में 2 के बाद अगली संख्या 3 है; 3 की वृद्धि में 3 से गिनती करके 3 के बाद सूची में प्रत्येक तीसरे नंबर को पार करें (ये सूची में 3 के सभी गुणक होंगे): 

2 3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

सूची में 3 के बाद जो अगली संख्या अभी तक नहीं निकली है वह 5 है; 5 की वृद्धि में 5 से गिनकर 5 के बाद सूची में प्रत्येक 5वीं संख्या को पार करें (अर्थात 5 के सभी गुणक): 

2 3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

5 के बाद सूची में अगली संख्या 7 है जिसे अभी तक नहीं काटा गया है; अगला कदम 7 के बाद सूची में प्रत्येक 7वीं संख्या को पार करना होगा, लेकिन वे सभी इस बिंदु पर प्रथम ही पार कर चुके हैं, क्योंकि ये संख्याएं (14, 21, 28) भी छोटी अभाज्य संख्याओं के गुणक हैं क्योंकि 7 × 7 बड़ा है 30 से अधिक। सूची में इस बिंदु पर जिन संख्याओं को नहीं काटा गया है, वे सभी 30 से नीचे की अभाज्य संख्याएँ हैं: 

2 3 5 7 11 13 17 19 23 29

एल्गोरिथम और वेरिएंट

स्यूडोकोड

एराटोस्थनीज की छलनी को स्यूडोकोड में व्यक्त किया जा सकता है, इस प्रकार है:[8][9] एराटोस्थनीज की छलनी एल्गोरिथम है 

    इनपुट: एक पूर्णांक n > 1.
    आउटपुट: 2 से n तक सभी अभाज्य संख्याएँ।

    चलो ए बूलियन डेटा प्रकार मानों की एक सरणी हो, पूर्णांक 2 से एन द्वारा अनुक्रमित,
    प्रारंभ में सभी सत्य पर सेट हैं।
    
    i के लिए = 2, 3, 4, ..., से अधिक नहीं √n करना
        अगर ए[आई] सच है
            जे = आई के लिए2, i2+i, i2+2i, i2+3i, ..., n 'do' से अधिक नहीं
                'सेट' ए [जे]: = 'गलत'

    'वापसी' सभी मैं ऐसा करता हूं कि ए [i] 'है' 'सत्य'।

यह एल्गोरिद्म इससे अधिक नहीं सभी अभाज्य संख्याएँ उत्पन्न करता है n. इसमें एक सामान्य अनुकूलन शामिल है, जो प्रत्येक अभाज्य के गुणकों की गणना करना प्रारम्भ करना है i से i2. इस एल्गोरिथम की समय जटिलता है O(n log log n),[9] बशर्ते सरणी अद्यतन एक है O(1) ऑपरेशन, जैसा कि आमतौर पर होता है।

खंडित छलनी

जैसा कि सोरेनसन नोट करते हैं, एराटोस्थनीज की छलनी के साथ समस्या इसके द्वारा किए जाने वाले संचालन की संख्या नहीं है, बल्कि इसकी मेमोरी आवश्यकताएं हैं।[9] बड़े के लिए n, हो सकता है कि अभाज्य संख्याओं की श्रेणी मेमोरी में फ़िट न हो; बदतर, मध्यम के लिए भी n, इसका CPU कैश उपयोग अत्यधिक उप इष्टतम है। एल्गोरिथ्म पूरे सरणी के माध्यम से चलता है A, संदर्भ की लगभग कोई स्थानीयता प्रदर्शित नहीं करता है।

इन समस्याओं का समाधान खंडित छलनी द्वारा प्रस्तुत किया जाता है, जहां एक समय में सीमा के केवल कुछ हिस्सों को छलनी किया जाता है।[10] ये 1970 के दशक से जाने जाते हैं, और निम्नानुसार काम करते हैं:[9][11]

  1. श्रेणी को 2 से विभाजित करें n कुछ आकार के खंडों में Δ ≤ √n.
  2. नियमित छलनी का उपयोग करके प्रथम (यानी सबसे कम) खंड में अभाज्य संख्याएँ खोजें।
  3. निम्न में से प्रत्येक खंड के लिए, बढ़ते क्रम में, के साथ m खंड का सर्वोच्च मान होने के कारण, इसमें अभाज्य संख्याएँ इस प्रकार खोजें:
    1. आकार की एक बूलियन सरणी सेट करें Δ.
    2. प्रत्येक प्राइम के गुणकों के अनुरूप सरणी में पदों को गैर-प्राइम के रूप में चिह्नित करें p ≤ √m के चरणों में इसके गुणकों की गणना करके अब तक पाया गया p के निम्नतम गुणज से प्रारम्भ करते हुए p बीच में m - Δ और m.
    3. सरणी में शेष गैर-चिह्नित स्थान खंड में primes के अनुरूप हैं। इन अभाज्य संख्याओं के किसी गुणज को चिन्हित करना आवश्यक नहीं है, क्योंकि ये सभी अभाज्य संख्याएँ इससे बड़ी हैं √m, से संबंधित k ≥ 1, किसी के पास .

अगर Δ को चुना गया है √n, एल्गोरिथम की भिन्नता िक्ष जटिलता है O(√n), जबकि समय की जटिलता नियमित छलनी के समान है।[9]

ऊपरी सीमा वाली श्रेणियों के लिए n इतना बड़ा कि छनाई नीचे की ओर चुभती है √n एराटोस्थनीज की पृष्ठ खंडित छलनी की आवश्यकता के अनुसार मेमोरी में फिट नहीं हो सकता है, इसके अतिरिक्त सोरेनसन की छलनी की तरह एक धीमी लेकिन अधिक स्थान-कुशल छलनी का उपयोग किया जा सकता है।[12]


वृद्धिशील छलनी

छलनी का एक वृद्धिशील सूत्रीकरण[2] उनके गुणकों की पीढ़ी के साथ प्राइम्स की पीढ़ी को अंतःस्थापित करके अनिश्चित काल तक (यानी, ऊपरी बाउंड के बिना) प्राइम उत्पन्न करता है (ताकि प्राइम को गुणकों के बीच भिन्नता ाल में पाया जा सके), जहां प्रत्येक प्राइम के गुणक p की वृद्धि में प्राइम के वर्ग से गिनती करके सीधे उत्पन्न होते हैं p (या 2p विषम अभाज्य संख्याओं के लिए)। दक्षता पर प्रतिकूल प्रभाव से बचने के लिए, पीढ़ी को केवल तभी प्रारम्भ किया जाना चाहिए जब प्राइम का वर्ग पहुंच गया हो। इसे डेटाफ्लो प्रोग्रामिंग प्रतिमान के तहत प्रतीकात्मक रूप से व्यक्त किया जा सकता है 

primes = [2, 3, ...] \ p², p²+p, ...] for p in primes],

साथ सूची बोध संकेतन का उपयोग करना \ पूरक (सेट सिद्धांत) # संख्याओं की अंकगणितीय प्रगति के सापेक्ष पूरक को दर्शाते हुए।

एक समय में एक प्राइम अनुक्रमिक प्राइम्स द्वारा ट्रायल डिवीजन के माध्यम से कंपोजिट को पुनरावृत्त रूप से छलनी करके भी प्राइम्स का उत्पादन किया जा सकता है। यह एराटोस्थनीज की छलनी नहीं है, लेकिन अक्सर इसके साथ भ्रमित होता है, भले ही एराटोस्थनीज की छलनी उनके लिए परीक्षण के अतिरिक्त सीधे कंपोजिट उत्पन्न करती है। ट्रायल डिवीजन में प्राइम्स की रेंज उत्पन्न करने में एराटोस्थनीज की छलनी की तुलना में एल्गोरिदम का बदतर सैद्धांतिक विश्लेषण है।[2]

प्रत्येक अभाज्य का परीक्षण करते समय, इष्टतम परीक्षण प्रभाग एल्गोरिथ्म सभी अभाज्य संख्याओं का उपयोग करता है जो इसके वर्गमूल से अधिक नहीं होती हैं, जबकि एराटोस्थनीज की छलनी प्रत्येक सम्मिश्र को केवल इसके प्रमुख कारकों से उत्पन्न करती है, और सम्मिश्रों के बीच मुफ्त में अभाज्य प्राप्त करती है। डेविड टर्नर (कंप्यूटर वैज्ञानिक) द्वारा व्यापक रूप से ज्ञात 1975 कार्यात्मक प्रोग्रामिंग चलनी कोड[13] अक्सर एराटोस्थनीज की छलनी के उदाहरण के रूप में प्रस्तुत किया जाता है[7]लेकिन वास्तव में एक उप-इष्टतम परीक्षण प्रभाग छलनी है।[2]


एल्गोरिथम जटिलता

एराटोस्थनीज की छलनी कंप्यूटर के प्रदर्शन को बेंचमार्क करने का एक लोकप्रिय तरीका है।[14] नीचे सभी अभाज्य संख्याओं की गणना करने की समय जटिलता n रैंडम एक्सेस मशीन मॉडल में है O(n log log n) संचालन, इस तथ्य का प्रत्यक्ष परिणाम है कि प्रमुख हार्मोनिक श्रृंखला स्पर्शोन्मुख रूप से पहुंचती है log log n. इसमें इनपुट आकार के संबंध में एक घातीय समय जटिलता है, चूँकि, जो इसे छद्म-बहुपद समय | छद्म-बहुपद एल्गोरिदम बनाता है। बुनियादी एल्गोरिदम की आवश्यकता है O(n) स्मृति का।

एल्गोरिदम की थोड़ी जटिलता है O(n (log n) (log log n)) बिट ऑपरेशंस की मेमोरी आवश्यकता के साथ O(n).[15] सामान्य रूप से लागू किए गए पृष्ठ खंडित संस्करण में समान परिचालन जटिलता होती है O(n log log n) गैर-खंडित संस्करण के रूप में लेकिन भिन्नता िक्ष आवश्यकताओं को खंड पृष्ठ के बहुत न्यूनतम आकार तक कम कर देता है और साथ ही आकार के क्रमिक पृष्ठ खंडों से कंपोजिट को कम करने के लिए उपयोग की जाने वाली श्रेणी के वर्गमूल से कम आधार प्राइम्स को स्टोर करने के लिए आवश्यक मेमोरी O(√n/log n).

एराटोस्थनीज की छलनी का एक विशेष (शायद ही कभी, यदि कभी, लागू किया गया) खंडित संस्करण, बुनियादी अनुकूलन के साथ, उपयोग करता है O(n) संचालन और O(√nlog log n/log n) स्मृति के टुकड़े।[16][17][18] बिग ओ नोटेशन का उपयोग करने से स्थिर कारकों और ऑफ़सेट की अनदेखी होती है जो व्यावहारिक श्रेणियों के लिए बहुत महत्वपूर्ण हो सकते हैं: एराटोस्थनीज भिन्नता की छलनी जिसे प्रिटचर्ड व्हील सीव के रूप में जाना जाता है[16][17][18]एक है O(n) प्रदर्शन, लेकिन इसके बुनियादी कार्यान्वयन के लिए या तो एक बड़ी सरणी एल्गोरिदम की आवश्यकता होती है जो इसकी प्रयोग करने योग्य सीमा को उपलब्ध स्मृति की मात्रा तक सीमित करती है अन्यथा स्मृति उपयोग को कम करने के लिए इसे पृष्ठ खंडित करने की आवश्यकता होती है। स्मृति को बचाने के लिए पेज सेगमेंटेशन के साथ कार्यान्वित किए जाने पर, मूल एल्गोरिदम को अभी भी आवश्यकता होती है O(n/log n) मेमोरी के बिट्स (एराटोस्थनीज के मूल पृष्ठ खंडित छलनी की आवश्यकता से बहुत अधिक O(√n/log n) स्मृति के टुकड़े)। प्रिटचर्ड के काम ने एक बड़े स्थिर कारक की कीमत पर स्मृति की आवश्यकता को कम कर दिया। चूँकि परिणामी पहिया छलनी है O(n) प्रदर्शन और एक स्वीकार्य स्मृति आवश्यकता, यह व्यावहारिक रूप से छानने की सीमा के लिए एराटोस्थनीज की यथोचित व्हील फैक्टराइज़्ड बुनियादी छलनी से तेज़ नहीं है।

यूलर की छलनी

रीमैन ज़ेटा फ़ंक्शन के लिए यूलर उत्पाद सूत्र का यूलर का प्रमाण # यूलर उत्पाद सूत्र के प्रमाण में एराटोस्थनीज़ की छलनी का एक संस्करण होता है जिसमें प्रत्येक समग्र संख्या ठीक एक बार समाप्त हो जाती है।[9]उसी छलनी को फिर से खोजा गया और रैखिक समय लेने के लिए मनाया गया Gries & Misra (1978).[19] यह भी, 2 से लेकर संख्याओं की सूची (कंप्यूटिंग) के साथ प्रारम्भ होता है n क्रम में। प्रत्येक चरण पर प्रथम तत्व को अगले अभाज्य के रूप में पहचाना जाता है, सूची के प्रत्येक तत्व से गुणा किया जाता है (इस प्रकार स्वयं से प्रारम्भ होता है), और परिणाम बाद में हटाने के लिए सूची में चिह्नित किए जाते हैं। प्रारंभिक तत्व और चिह्नित तत्वों को कार्य क्रम से हटा दिया जाता है, और प्रक्रिया दोहराई जाती है:

[2] (3) 5 7 <यू>9</यू> 11 13 <यू>15</यू> 17 19 <यू>21</यू> 23 25 <यू>27</यू> 29 31 <यू >33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 ... 

[3] (5) 7 11 13 17 19 23 <यू>25</यू> 29 31 <यू>35</यू> 37 41 43 47 49 53 <यू>55</यू> 59 61 <यू>65 </यू> 67 71 73 77 79 ...
[4] (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 ...
[5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ...
[...]

यहाँ उदाहरण को एल्गोरिथम के प्रथम चरण के बाद ऑड्स से प्रारम्भ करते हुए दिखाया गया है। इस प्रकार, पर kवाँ चरण के सभी शेष गुणज kवें अभाज्य को सूची से हटा दिया जाता है, जिसमें बाद में प्रथम के साथ केवल सहअभाज्य संख्याएँ होंगी k primes (cf. Wheel factorization), ताकि सूची अगले अभाज्य से प्रारम्भ हो, और इसके प्रथम तत्व के वर्ग के नीचे की सभी संख्याएँ भी अभाज्य होंगी।

इस प्रकार, अभाज्य संख्याओं का एक बंधा हुआ अनुक्रम उत्पन्न करते समय, जब अगली पहचानी गई अभाज्य ऊपरी सीमा के वर्गमूल से अधिक हो जाती है, तो सूची में शेष सभी संख्याएँ अभाज्य होती हैं।[9]ऊपर दिए गए उदाहरण में 11 को अगले अभाज्य के रूप में पहचानने पर, 80 से कम या उसके समान सभी अभाज्य संख्याओं की सूची देकर प्राप्त किया जाता है।

ध्यान दें कि किसी चरण द्वारा छोड़ी जाने वाली संख्याएँ अभी भी उस चरण में गुणकों को चिह्नित करते समय उपयोग की जाती हैं, उदाहरण के लिए, 3 के गुणकों के लिए यह है 3 × 3 = 9, 3 × 5 = 15, 3 × 7 = 21, 3 × 9 = 27, ..., 3 × 15 = 45, ..., इसलिए इससे निपटने में सावधानी बरतनी चाहिए।[9]


यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 1.2 Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," Philosophical Transactions (1683–1775), Vol. 62. (1772), pp. 327–347.
  2. ↑ 2.0 2.1 2.2 2.3 O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004, pp. 10, 11 (contains two incremental sieves in Haskell: a priority-queue–based one by O'Neill and a list–based, by Richard Bird).
  3. ↑ Hoche, Richard, ed. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, chapter XIII, 3, Leipzig: B.G. Teubner, p. 30
  4. ↑ 4.0 4.1 Nicomachus of Gerasa (1926), Introduction to Arithmetic; translated into English by Martin Luther D'Ooge ; with studies in Greek arithmetic by Frank Egleston Robbins and Louis Charles Karpinski, chapter XIII, 3, New York: The Macmillan Company, p. 204
  5. ↑ J. C. Morehead, "Extension of the Sieve of Eratosthenes to arithmetical progressions and applications", Annals of Mathematics, Second Series 10:2 (1909), pp. 88–104.
  6. ↑ Clocksin, William F., Christopher S. Mellish, Programming in Prolog, 1984, p. 170. ISBN 3-540-11046-1.
  7. ↑ 7.0 7.1 Runciman, Colin (1997). "Functional Pearl: Lazy wheel sieves and spirals of primes" (PDF). Journal of Functional Programming. 7 (2): 219–225. doi:10.1017/S0956796897002670. S2CID 2422563.
  8. ↑ Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN 978-0-201-51059-1., p. 16.
  9. ↑ 9.0 9.1 9.2 9.3 9.4 9.5 9.6 9.7 Jonathan Sorenson, An Introduction to Prime Number Sieves, Computer Sciences Technical Report #909, Department of Computer Sciences University of Wisconsin-Madison, January 2, 1990 (the use of optimization of starting from squares, and thus using only the numbers whose square is below the upper limit, is shown).
  10. ↑ Crandall & Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer: 2005, pp. 121–24.
  11. ↑ Bays, Carter; Hudson, Richard H. (1977). "The segmented sieve of Eratosthenes and primes in arithmetic progressions to 1012". BIT. 17 (2): 121–127. doi:10.1007/BF01932283. S2CID 122592488.
  12. ↑ J. Sorenson, "The pseudosquares prime sieve", Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).
  13. ↑ Turner, David A. SASL language manual. Tech. rept. CS/75/1. Department of Computational Science, University of St. Andrews 1975. (primes = sieve [2..]; sieve (p:nos) = p:sieve (remove (multsof p) nos); remove m = filter (not . m); multsof p n = rem n p==0). But see also Peter Henderson, Morris, James Jr., A Lazy Evaluator, 1976, where we find the following, attributed to P. Quarendon: primeswrt[x;l] = if car[l] mod x=0 then primeswrt[x;cdr[l]] else cons[car[l];primeswrt[x;cdr[l]]] ; primes[l] = cons[car[l];primes[primeswrt[car[l];cdr[l]]]] ; primes[integers[2]]; the priority is unclear.
  14. ↑ Peng, T. A. (Fall 1985). "चलनी के माध्यम से एक मिलियन प्राइम्स". BYTE. pp. 243–244. Retrieved 19 March 2016.
  15. ↑ Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci. Comput. Programming 9:1 (1987), pp. 17–35.
  16. ↑ 16.0 16.1 Paul Pritchard, "A sublinear additive sieve for finding prime numbers", Communications of the ACM 24 (1981), 18–23. MR600730
  17. ↑ 17.0 17.1 Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. MR685983
  18. ↑ 18.0 18.1 Paul Pritchard, "Fast compact prime number sieves" (among others), Journal of Algorithms 4 (1983), 332–344. MR729229
  19. ↑ Gries, David; Misra, Jayadev (December 1978), "A linear sieve algorithm for finding prime numbers" (PDF), Communications of the ACM, 21 (12): 999–1003, doi:10.1145/359657.359660, hdl:1813/6407, S2CID 11990373.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एराटोस्थनीज_की_छलनी&oldid=193488’