View source for एराटोस्थनीज की छलनी

{{short description|Ancient algorithm for generating prime numbers}}
{{For|मूर्तिकला|एराटोस्थनीज की छलनी (मूर्तिकला)}}
[[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" /> प्रत्येक अनुशोधित अभाज्य संख्याओं के सभी गुणकों को कंपोजिट के रूप में चिह्नित किया गया है, शेष अचिह्नित संख्याएं अभाज्य संख्याएं हैं।

सीव का सबसे प्रथम ज्ञात संदर्भ (कोस्किनॉन एराटोस्थेनस) अंकगणित के [[निकोमाचस]] के परिचय में,<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 समुच्चय है। सीई पुस्तक जो इसका श्रेय एराटोस्थनीज को देती है, जो कि तीसरा प्रतिशत है। ईसा पूर्व [[ग्रीक गणित|ग्रीक गणितज्ञ]], चूँकि अभाज्य संख्याओं के अतिरिक्त विषम संख्याओं द्वारा सीव का वर्णन करता है।<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>



== अवलोकन ==
{{quote box|fontsize = 105%|''दो को छानें और तीन को छान लें:''<br />''एरेटोस्थनीज की छलनी।''<br />''जब गुणज उदात्त हों,''<br />''जो अंक रह जाते हैं वे अभाज्य हैं। ''|quoted=1|salign=center|source=Anonymous<ref>Clocksin, William F., Christopher S. Mellish, ''Programming in Prolog'', 1984, p.&nbsp;170. {{isbn|3-540-11046-1}}.</ref>}}

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

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

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

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

परिशोधन के रूप में, {{math|''p''<sup>2</sup>}} से प्रारंभ करते हुए चरण 3 में संख्याओं को चिह्नित करना पर्याप्त है, क्योंकि {{mvar|p}} के सभी छोटे गुणकों को उस बिंदु पर पहले ही चिह्नित किया जा चुका होगा। इसका अर्थ है कि एल्गोरिथम को चरण 4 में समाप्त करने की अनुमति है जब {{math|''p''<sup>2</sup>}} से {{mvar|n}} अधिक है।<ref name="horsley" /> 

परिशोधन प्रारम्भ में केवल विषम संख्याओं को सूचीबद्ध करना है, {{math|(3, 5, ..., ''n'')}}, और चरण 3 में {{math|2''p''}} की वृद्धि में गणना करें, इस प्रकार {{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 के समान सभी अभाज्य संख्याएँ ज्ञात करने के लिए, निम्नानुसार आगे बढ़ें।

सबसे प्रथम, 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 {{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 है; 3 की वृद्धि में 3 से गिनती करके 3 के पश्चात सूची में प्रत्येक तीसरे नंबर से आगे जाएं  (ये सूची में 3 के सभी गुणक होंगे):

 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>}} 25 {{gray|<s>26 </s>}}{{gray|<s>27 </s>}}{{gray|<s>28</s>}} 29 {{gray|<s>30</s>}}

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

 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 से नीचे की अभाज्य संख्याएँ हैं:

 2 3 5 7 11 13 17 19 23 29

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

=== [[स्यूडोकोड]] ===
एराटोस्थनीज की सीव को स्यूडोकोड में व्यक्त किया जा सकता है, <ref name="sedgewick">{{cite book
|last1=Sedgewick |first1=Robert |title=Algorithms in C++
|publisher=Addison-Wesley |year=1992 |isbn=978-0-201-51059-1 
}}, p.&nbsp;16.</ref><ref name="intro">[http://research.cs.wisc.edu/techreports/1990/TR909.pdf 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).</ref>एराटोस्थनीज की सीव एल्गोरिथम इस प्रकार है:
     '''algorithm''' Sieve of Eratosthenes '''is'''

 
     '''input''': an integer ''n'' > 1.

  '''output''': all prime numbers from 2 through ''n''.
      '''let''' ''A'' be an '''array of'''  [[बूलियन डेटा प्रकार|'''Boolean''' values]] , indexed by '''integer'''s 2 to ''n'',

     initially all '''set''' to '''true'''.
         
     '''for''' ''i'' = 2, 3, 4, ..., not exceeding ''√n'' '''do'''
         '''if''' ''A''[''i''] '''is''' '''true'''
            '''for''' ''j'' = ''i''<sup>2</sup>, ''i''<sup>2</sup>+''i'', ''i''<sup>2</sup>+2''i'', ''i''<sup>2</sup>+3''i'', ..., not exceeding ''n'' '''do'''
                 '''set''' ''A''[''j''] := '''false'''
 
     '''return''' all ''i'' such that ''A''[''i''] '''is''' '''true'''.
यह एल्गोरिद्म {{mvar|n}}  से अधिक नहीं सभी अभाज्य संख्याएँ उत्पन्न करता है। इसमें सामान्य अनुकूलन सम्मिलित है, जो {{math|''i''<sup>2</sup>}} से प्रत्येक अभाज्य {{mvar|i}} के गुणकों की गणना करना प्रारंभ करना है। इस एल्गोरिथम की [[समय जटिलता]] {{math|''O''(''n'' log log ''n'')}} है,{{r|intro}} परन्तु सरणी अद्यतन {{math|''O''(1)}} ऑपरेशन है, जैसा कि सामान्यतः होता है।

=== खंडित सीव ===
जिस प्रकार सोरेनसन नोट करते हैं, एराटोस्थनीज की सीव के साथ समस्या इसके द्वारा किए जाने वाले संचालन की संख्या नहीं है, चूँकि इसकी मेमोरी आवश्यकताएं हैं।{{r|intro}} बड़े {{mvar|n}} के लिए, अभाज्य संख्याओं की श्रेणी मेमोरी में फ़िट न हो; अन्य मध्यम {{mvar|n}} के लिए भी, इसका सीपीयू कैश उपयोग अत्यधिक उप इष्टतम है। एल्गोरिथ्म पूर्ण सरणी {{mvar|A}} के माध्यम से चलता है, संदर्भ के लगभग कोई स्थानीयता प्रदर्शित नहीं करता है।

इन समस्याओं का समाधान खंडित सीव द्वारा प्रस्तुत किया जाता है, जहां समय में सीमा के केवल कुछ भागों को सीव किया जाता है।<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''}}}} के किसी आकार के खंडों में विभाजित करें।
# नियमित सीव का उपयोग करके प्रथम (अर्थात सबसे कम) खंड में अभाज्य संख्याएँ का परीक्षण करते है।
# निम्न में से प्रत्येक खंड के लिए, बढ़ते क्रम में, {{mvar|m}} खंड का सर्वोच्च मान होने के कारण, इसमें अभाज्य संख्याएँ का परीक्षण इस प्रकार करते है:
## {{math|Δ}} आकार की बूलियन सरणी सेट करें।
## अब तक पाए गए प्रत्येक अभाज्य {{math|''p'' ≤ {{sqrt|''m''}}}} के गुणकों के अनुरूप सरणी में गैर-अभाज्य के रूप में चिह्नित करें, {{math|{{mvar|m}} - Δ}} और {{mvar|m}} के मध्य {{math|''p''}} के निम्नतम गुणज से प्रारम्भ करते हुए {{math|''p''}} के चरणों में इसके गुणकों की गणना करते है।
## सरणी में शेष अन्य-चिह्नित स्थान खंड में अभाज्य संख्याओं के अनुरूप हैं। इन अभाज्य संख्याओं के किसी गुणज को चिन्हित करना आवश्यक नहीं है, क्योंकि ये सभी अभाज्य संख्याएँ {{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|''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''}} विषम अभाज्य संख्याओं के लिए) की वृद्धि में अभाज्य संख्याओं के वर्ग से गिनती करके सीधे उत्पन्न होते हैं। दक्षता पर प्रतिकूल प्रभाव से बचने के लिए, पीढ़ी को केवल तभी प्रारम्भ किया जाना चाहिए जब अभाज्य संख्याओं का वर्ग पहुंच गया हो। इसे [[डेटाफ्लो प्रोग्रामिंग]] प्रतिमान के अंतर्गत प्रतीकात्मक रूप से व्यक्त किया जा सकता है

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

संख्याओं की [[अंकगणितीय प्रगति]] के सेट घटाव को दर्शाने वाले <code>\</code> के साथ सूची बोध संकेतन का उपयोग करना।  

अभाज्य संख्याओं अनुक्रमिक अभाज्य द्वारा विभाज्यता परीक्षण के माध्यम से कंपोजिट को पुनरावृत्त रूप से सीव करके भी अभाज्य संख्याओं का उत्पादन किया जा सकता है। यह एराटोस्थनीज की सीव नहीं है, परन्तु प्रायः इसके साथ भ्रमित होता है, एराटोस्थनीज की सीव उनके लिए परीक्षण के अतिरिक्त सीधे कंपोजिट उत्पन्न करती है। विभाज्यता परीक्षण में अभाज्य संख्याओं की श्रेणी उत्पन्न करने में एराटोस्थनीज की सीव की अपेक्षा में एल्गोरिदम का सैद्धांतिक विश्लेषण है।<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"/>


== एल्गोरिथम जटिलता ==
एराटोस्थनीज की सीव कंप्यूटर के प्रदर्शन को बेंचमार्क करने का लोकप्रिय उपाय है।<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''(''n'')}} की मेमोरी आवश्यकता के साथ {{math|''O''<big>(</big>''n'' (log ''n'') (log log ''n'')<big>)</big>}} बिट संचालन है।<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'')}} संचालन और {{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>[[बिग ओ नोटेशन]] का उपयोग निरंतर कारकों और ऑफसेट को अनदेखा करता है जो व्यावहारिक श्रेणियों के लिए अधिक महत्वपूर्ण हो सकते हैं: प्रिटचर्ड व्हील सीव के रूप में जाना जाने वाला एराटोस्थनीज भिन्नता की सीव में <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="intro" />उसी सीव को फिर से अनुशोधित किया गया और  {{harvtxt|ग्रिस|मिश्रा|1978}} [[रैखिक समय]] लेने के लिए मनाया गया.<ref>{{citation
 | last1 = Gries | first1 = David | author1-link = David Gries
 | last2 = Misra | first2 = Jayadev
 | date = December 1978
 | doi = 10.1145/359657.359660
 | issue = 12
 | journal = [[Communications of the ACM]]
 | pages = 999–1003
 | title = A linear sieve algorithm for finding prime numbers
 | volume = 21| hdl = 1813/6407 | s2cid = 11990373 | url = https://ecommons.cornell.edu/bitstream/1813/6407/1/77-313.pdf
 | hdl-access = free
 }}.</ref> यह भी, 2 से लेकर संख्याओं की [[सूची (कंप्यूटिंग)]] के साथ {{mvar|n}} क्रम में प्रारम्भ होता है। प्रत्येक चरण पर प्रथम तत्व को निकटतम अभाज्य के रूप में पहचाना जाता है, सूची के प्रत्येक तत्व से गुणा किया जाता है (इस प्रकार स्वयं से प्रारम्भ होता है), और परिणाम पश्चात में हटाने के लिए सूची में चिह्नित किए जाते हैं। प्रारंभिक तत्व और चिह्नित तत्वों को कार्य क्रम से हटा दिया जाता है, और प्रक्रिया दोहराई जाती है:
<div शैली = फ़ॉन्ट-आकार: 85%; >  

  [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  [...]

</div>

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

इस प्रकार, अभाज्य संख्य[[प्रिचर्ड की छलनी|छलनी]] का बंधा हुआ [[एटकिन की छलनी|छलनी]]क्रम उत्पन्न क[[सुंदरम की छलनी|छलनी]] समय, जब निकटतम पहचानी गई अभाज्य ऊपरी सीमा के वर्गमूल से अधिक हो जाती है, तो सूची में शेष सभी संख्याएँ अभाज्य होती हैं।<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" />


== यह भी देखें ==
* [[प्रिचर्ड की छलनी|प्रिचर्ड की सीव]]
* [[एटकिन की छलनी|एटकिन की सीव]]
* [[सुंदरम की छलनी|सुंदरम की सीव]]
* सीव [[चलनी सिद्धांत|सिद्धांत]]

==संदर्भ==
{{Reflist|2}}


==बाहरी संबंध==
* [http://primesieve.org/ अभाज्य संख्याieve – Very fast highly optimized C/C++ segmented Sieve of Eratosthenes]
* [https://www.encyclopediaofmath.org/index.php/Eratosthenes,_sieve_of ''Eratosthenes, sieve of'' at Encyclopaedia of Mathematics]
* [http://www.hbmeyer.de/eratosiv.htm Interactive JavaScript Page]
* [http://demonstrations.wolfram.com/SieveOfEratosthenes/ Sieve of Eratosthenes] by George Beck, [[Wolfram Demonstrations Project]].
* [https://wiki.haskell.org/Prime_numbers#Sieve_of_Eratosthenes Sieve of Eratosthenes in Haskell]
* [http://www.algolist.net/Algorithms/Number_theoretic_algorithms/Sieve_of_Eratosthenes Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.]
* [http://zsmith.co/primes.html A related sieve written in x86 assembly language]
* [https://sites.google.com/site/bbuhrow/home/cuda-sieve-of-eratosthenes Fast optimized highly parallel  CUDA segmented Sieve of Eratosthenes in C]
* [http://wiki.c2.com/?SieveOfEratosthenesInManyProgrammingLanguages SieveOfEratosthenesInManyProgrammingLanguages c2 wiki page]
* [http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html The Art of Prime Sieving] Sieve of Eratosthenes in C from 1998 with nice features and algorithmic tricks explained.

{{number theoretic algorithms}}

{{DEFAULTSORT:Sieve Of Eratosthenes}}[[Category: प्रधानता परीक्षण]] [[Category: स्यूडोकोड के उदाहरण वाले लेख]] [[Category: चलनी सिद्धांत | चलनी सिद्धांत ]] [[Category: एल्गोरिदम]] 



[[Category: Machine Translated Page]]
[[Category:Created On 01/06/2023]]