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

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


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


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


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


=== [[स्यूडोकोड]] ===
=== [[स्यूडोकोड]] ===
एराटोस्थनीज की सीव को स्यूडोकोड में व्यक्त किया जा सकता है, <ref name="sedgewick">{{cite book
एराटोस्थनीज की छलनी को स्यूडोकोड में व्यक्त किया जा सकता है, <ref name="sedgewick">{{cite book
|last1=Sedgewick |first1=Robert |title=Algorithms in C++
|last1=Sedgewick |first1=Robert |title=Algorithms in C++
|publisher=Addison-Wesley |year=1992 |isbn=978-0-201-51059-1  
|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>एराटोस्थनीज की सीव एल्गोरिथम इस प्रकार है:
}}, 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'''
     '''algorithm''' Sieve of Eratosthenes '''is'''


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


Line 80: Line 78:
यह एल्गोरिद्म {{mvar|n}}  से अधिक नहीं सभी अभाज्य संख्याएँ उत्पन्न करता है। इसमें सामान्य अनुकूलन सम्मिलित है, जो {{math|''i''<sup>2</sup>}} से प्रत्येक अभाज्य {{mvar|i}} के गुणकों की गणना करना प्रारंभ करना है। इस एल्गोरिथम की [[समय जटिलता]] {{math|''O''(''n'' log log ''n'')}} है,{{r|intro}} परन्तु सरणी अद्यतन {{math|''O''(1)}} ऑपरेशन है, जैसा कि सामान्यतः होता है।
यह एल्गोरिद्म {{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}} के माध्यम से चलता है, संदर्भ के लगभग कोई स्थानीयता प्रदर्शित नहीं करता है।
जिस प्रकार सोरेनसन नोट करते हैं, एराटोस्थनीज की छलनी के साथ समस्या इसके द्वारा किए जाने वाले संचालन की संख्या नहीं है, चूँकि इसकी मेमोरी आवश्यकताएं हैं।{{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>
इन समस्याओं का समाधान खंडित छलनी द्वारा प्रस्तुत किया जाता है, जहां समय में सीमा के केवल कुछ भागों को छलनी किया जाता है।<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|Δ}} आकार की बूलियन सरणी सेट करें।
Line 91: Line 89:
## सरणी में शेष अन्य-चिह्नित स्थान खंड में अभाज्य संख्याओं के अनुरूप हैं। इन अभाज्य संख्याओं के किसी गुणज को चिन्हित करना आवश्यक नहीं है, क्योंकि ये सभी अभाज्य संख्याएँ {{math|{{sqrt|''m''}}}}, से बड़ी हैं, जैसा कि {{math|''k'' ≥ 1}}, के लिए, किसी के समीप <math>(k\Delta + 1)^2 > (k+1)\Delta</math> है।
## सरणी में शेष अन्य-चिह्नित स्थान खंड में अभाज्य संख्याओं के अनुरूप हैं। इन अभाज्य संख्याओं के किसी गुणज को चिन्हित करना आवश्यक नहीं है, क्योंकि ये सभी अभाज्य संख्याएँ {{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 104: Line 102:
संख्याओं की [[अंकगणितीय प्रगति]] के सेट घटाव को दर्शाने वाले <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"/>




== एल्गोरिथम जटिलता ==
== एल्गोरिथम जटिलता ==
एराटोस्थनीज की सीव कंप्यूटर के प्रदर्शन को बेंचमार्क करने का लोकप्रिय उपाय है।<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''(''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'')}} की मेमोरी आवश्यकता के साथ {{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'' 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>[[बिग ओ नोटेशन]] का उपयोग निरंतर कारकों और ऑफसेट को अनदेखा करता है जो व्यावहारिक श्रेणियों के लिए अधिक महत्वपूर्ण हो सकते हैं: प्रिटचर्ड व्हील सीव के रूप में जाना जाने वाला एराटोस्थनीज भिन्नता की सीव में <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'')}} प्रदर्शन है और स्वीकार्य स्मृति आवश्यकता, यह व्यावहारिक रूप से सीव की सीमा के लिए एराटोस्थनीज की यथोचित व्हील फैक्टराइज़्ड मूलभूत सीव से तीव्र नहीं है।
(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
जीटा उत्पाद सूत्र के यूलर के प्रमाण में एराटोस्थनीज की छलनी का संस्करण सम्मिलित होता है जिसमें प्रत्येक समग्र संख्या को विस्थापित कर दिया जाता है। {{harvtxt|ग्रिस|मिश्रा|1978}} द्वारा उसी छलनी को फिर से अनुशोधित किया गया और [[रैखिक समय]] लेने के लिए देखा गया।<ref>{{citation
  | last1 = Gries | first1 = David | author1-link = David Gries
  | last1 = Gries | first1 = David | author1-link = David Gries
  | last2 = Misra | first2 = Jayadev
  | last2 = Misra | first2 = Jayadev
Line 131: Line 129:
  | 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%; >   


Line 141: Line 139:
</div>
</div>


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


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




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


==संदर्भ==
==संदर्भ==
Line 172: Line 170:
{{number theoretic algorithms}}
{{number theoretic algorithms}}


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


[[Category: Machine Translated Page]]
[[Category:Articles containing Greek-language text]]
[[Category:Created On 01/06/2023]]
[[Category:Articles with hatnote templates targeting a nonexistent page|Sieve Of Eratosthenes]]
[[Category:Collapse templates|Sieve Of Eratosthenes]]
[[Category:Created On 01/06/2023|Sieve Of Eratosthenes]]
[[Category:Lua-based templates|Sieve Of Eratosthenes]]
[[Category:Machine Translated Page|Sieve Of Eratosthenes]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|Sieve Of Eratosthenes]]
[[Category:Pages with script errors|Sieve Of Eratosthenes]]
[[Category:Sidebars with styles needing conversion|Sieve Of Eratosthenes]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Translated in Hindi|Sieve Of Eratosthenes]]
[[Category:Templates Vigyan Ready|Sieve Of Eratosthenes]]
[[Category:Templates generating microformats|Sieve Of Eratosthenes]]
[[Category:Templates that add a tracking category|Sieve Of Eratosthenes]]
[[Category:Templates that are not mobile friendly|Sieve Of Eratosthenes]]
[[Category:Templates that generate short descriptions|Sieve Of Eratosthenes]]
[[Category:Templates using TemplateData|Sieve Of Eratosthenes]]
[[Category:Wikipedia metatemplates|Sieve Of Eratosthenes]]
[[Category:एल्गोरिदम|Sieve Of Eratosthenes]]
[[Category:चलनी सिद्धांत| चलनी सिद्धांत ]]
[[Category:प्रधानता परीक्षण|Sieve Of Eratosthenes]]
[[Category:स्यूडोकोड के उदाहरण वाले लेख|Sieve Of Eratosthenes]]

Latest revision as of 14:54, 31 October 2023

एराटोस्थनीज की छलनी: 121 से नीचे के अभाज्यों के लिए एल्गोरिथम चरण (अभाज्य संख्याओं के वर्ग से प्रारम्भ करने के अनुकूलन सहित) है।

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

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

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

कई अभाज्य संख्याओं में से, यह सभी छोटे अभाज्यों को शोध के सबसे कुशल उपाय है। इसका उपयोग अंकगणितीय प्रगति में अभाज्य संख्या की अनुशोधन के लिए किया जा सकता है।[5]


अवलोकन

दो को छानें और तीन को छान लें:
एरेटोस्थनीज की सीव।
जब गुणज उदात्त हों,
जो अंक रह जाते हैं वे अभाज्य हैं।

अनाम[6]

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

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

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

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

परिशोधन के रूप में, p2 से प्रारंभ करते हुए चरण 3 में संख्याओं को चिह्नित करना पर्याप्त है, क्योंकि p के सभी छोटे गुणकों को उस बिंदु पर पहले ही चिह्नित किया जा चुका होगा। इसका अर्थ है कि एल्गोरिथम को चरण 4 में समाप्त करने की अनुमति है जब p2 से n अधिक है।[1]

परिशोधन प्रारम्भ में केवल विषम संख्याओं को सूचीबद्ध करना है, (3, 5, ..., n), और चरण 3 में 2p की वृद्धि में गणना करें, इस प्रकार 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]एराटोस्थनीज की छलनी एल्गोरिथम इस प्रकार है: 

    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 integers 2 to n,

    initially all set to true.
        
    for i = 2, 3, 4, ..., not exceeding √n do
        if A[i] is true
           for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
                set A[j] := false

    return all i such that A[i] is true.

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

खंडित छलनी

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

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

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

यूलर की छलनी

जीटा उत्पाद सूत्र के यूलर के प्रमाण में एराटोस्थनीज की छलनी का संस्करण सम्मिलित होता है जिसमें प्रत्येक समग्र संख्या को विस्थापित कर दिया जाता है। ग्रिस & मिश्रा (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वें चरण पर kth अभाज्य के सभी शेष गुणकों को सूची से विस्थापित कर दिया जाता है, जिसमें पश्चात में प्रथम k अभाज्यों (cf. व्हील फैक्टराइजेशन), के साथ केवल संख्याएँ सम्मिलित होंगी, जिससे कि सूची अगले अभाज्य के साथ प्रारंभ हो सके, और इसके पहले एलिमेंट के वर्ग के नीचे की सभी संख्याएँ भी अभाज्य होंगी।

इस प्रकार, अभाज्य संख्याओं के परिबद्ध अनुक्रम को उत्पन्न करते समय, जब अगला चिन्हित अभाज्य ऊपरी सीमा के वर्गमूल से अधिक हो जाता है, तो सूची में शेष सभी संख्याएँ अभाज्य होती हैं। ऊपर दिए गए उदाहरण में 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 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=271867’