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

Revision as of 11:57, 10 June 2023

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

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

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

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

सिंहावलोकन

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

Anonymous^[6]

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

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

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

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

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

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

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

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

खंडित छलनी

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

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

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

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

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

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

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

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(.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}√n/log n)$ है।

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

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

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

यह भी देखें

संदर्भ

↑ ^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.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).
↑ Hoche, Richard, ed. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, chapter XIII, 3, Leipzig: B.G. Teubner, p. 30
↑ ^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
↑ 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.
↑ Clocksin, William F., Christopher S. Mellish, Programming in Prolog, 1984, p. 170. ISBN 3-540-11046-1.
↑ ^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.
↑ Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN 978-0-201-51059-1., p. 16.
↑ ^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).
↑ Crandall & Pomerance, Prime Numbers: A Computational Perspective, second edition, Springer: 2005, pp. 121–24.
↑ Bays, Carter; Hudson, Richard H. (1977). "The segmented sieve of Eratosthenes and primes in arithmetic progressions to 10¹²". BIT. 17 (2): 121–127. doi:10.1007/BF01932283. S2CID 122592488.
↑ J. Sorenson, "The pseudosquares prime sieve", Proceedings of the 7th International Symposium on Algorithmic Number Theory. (ANTS-VII, 2006).
↑ 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.
↑ Peng, T. A. (Fall 1985). "चलनी के माध्यम से एक मिलियन प्राइम्स". BYTE. pp. 243–244. Retrieved 19 March 2016.
↑ Pritchard, Paul, "Linear prime-number sieves: a family tree," Sci. Comput. Programming 9:1 (1987), pp. 17–35.
↑ ^16.0 ^16.1 Paul Pritchard, "A sublinear additive sieve for finding prime numbers", Communications of the ACM 24 (1981), 18–23. MR600730
↑ ^17.0 ^17.1 Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. MR685983
↑ ^18.0 ^18.1 Paul Pritchard, "Fast compact prime number sieves" (among others), Journal of Algorithms 4 (1983), 332–344. MR729229
↑ 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.

बाहरी संबंध

primesieve – Very fast highly optimized C/C++ segmented Sieve of Eratosthenes
Eratosthenes, sieve of at Encyclopaedia of Mathematics
Interactive JavaScript Page
Sieve of Eratosthenes by George Beck, Wolfram Demonstrations Project.
Sieve of Eratosthenes in Haskell
Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.
A related sieve written in x86 assembly language
Fast optimized highly parallel CUDA segmented Sieve of Eratosthenes in C
SieveOfEratosthenesInManyProgrammingLanguages c2 wiki page
The Art of Prime Sieving Sieve of Eratosthenes in C from 1998 with nice features and algorithmic tricks explained.

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

[ONeill-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).

[nicomachus-3] Hoche, Richard, ed. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, chapter XIII, 3, Leipzig: B.G. Teubner, p. 30

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

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

[sedgewick-8] Sedgewick, Robert (1992). Algorithms in C++. Addison-Wesley. ISBN 978-0-201-51059-1., p. 16.

[intro-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 10¹²". 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.

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

[Pritchard1-16] 16.0 ^16.1 Paul Pritchard, "A sublinear additive sieve for finding prime numbers", Communications of the ACM 24 (1981), 18–23. MR600730

[Pritchard2-17] 17.0 ^17.1 Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. MR685983

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

@@ Line 109: / Line 109: @@
 एराटोस्थनीज की छलनी का विशेष (यदि कभी, प्रस्तावित किया गया) खंडित संस्करण, बुनियादी अनुकूलन के साथ, {{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="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 132: / Line 132: @@
 </div>
-यहाँ उदाहरण को एल्गोरिथम के प्रथम चरण के पश्चात ऑड्स से प्रारम्भ करते हुए दिखाया गया है। इस प्रकार, पर {{mvar|k}} वाँ चरण के सभी शेष गुणज {{mvar|k}} अभाज्य को सूची से हटा दिया जाता है, जिसमें पश्चात में प्रथम के साथ केवल सहअभाज्य संख्याएँ होंगी {{mvar|k}} अभाज्य संख्याओं (cf. Wheel factorization), जिससे सूची  निकटतम अभाज्य से प्रारम्भ हो, और इसके प्रथम तत्व के वर्ग के नीचे की सभी संख्याएँ भी अभाज्य होंगी।
+यहाँ उदाहरण को एल्गोरिथम के प्रथम चरण के पश्चात ऑड्स से प्रारम्भ करते हुए दिखाया गया है। इस प्रकार, पर {{mvar|k}} वाँ चरण के सभी शेष गुणज {{mvar|k}} अभाज्य को सूची से हटा दिया जाता है, पश्चात में प्रथम के साथ केवल सहअभाज्य संख्याएँ होंगी {{mvar|k}} अभाज्य संख्याओं (सी एफ व्हील फैक्टराइजेशन), जिससे सूची  निकटतम अभाज्य से प्रारम्भ हो, और इसके प्रथम तत्व के वर्ग के नीचे की सभी संख्याएँ भी अभाज्य होंगी।
 इस प्रकार, अभाज्य संख्याओं का बंधा हुआ अनुक्रम उत्पन्न करते समय, जब निकटतम पहचानी गई अभाज्य ऊपरी सीमा के वर्गमूल से अधिक हो जाती है, तो सूची में शेष सभी संख्याएँ अभाज्य होती हैं।<ref name="intro" />ऊपर दिए गए उदाहरण में 11 को  निकटतम अभाज्य के रूप में पहचानने पर, 80 से कम या उसके समान  सभी अभाज्य संख्याओं की सूची देकर प्राप्त किया जाता है।

v t e संख्या-सिद्धांत एल्गोरिथ्म
प्राइमैलिटी टेस्ट	AKS अप्रैल BAILLIE -PSW अण्डाकार वक्र पॉकलिंगटन Fermat लुकास लुकास -लेहमेर लुकास -लेहमेर -रेज़ल ' प्रोथ का प्रमेय पेपिन का द्विघात फ्रोबेनियस सोलोवे -स्ट्रासेन मिलर -रबिन
प्राइम-जनरेटिंग	एटकिन की छलनी एरातोस्टेनेस की छलनी प्रिचर्ड की छलनी सुंदरम की छलनी पहिया कारक
पूर्णांक कारक	निरंतर अंश कारक। निरंतर अंश (CFRAC) डिक्सन Lenstra अण्डाकार-वक्र कारक Euler's पोलार्ड्स आरएचओ P - 1 पी + 1 द्विघात छलनी (क्यूएस) सामान्य संख्या क्षेत्र छलनी (GNFS) विशेष संख्या क्षेत्र छलनी (SNFS) तर्कसंगत छलनी फर्माट शैंक्स स्क्वायर फॉर्म ट्रायल डिवीजन शोर
गुणा	प्राचीन मिस्र लंबा करत्सुबा टूम - कुक Schönhage - Strassen Für's
Euclidean डिवीजन	बाइनरी चंकिंग फूरियर Goldschmidt न्यूटन-रफसन लंबा छोटा SRT
असतत लघुगणक	बेबी-स्टेप विशाल-चरण पोलार्ड रो पोलार्ड कंगारू Pohlig -Hellman इंडेक्स कैलकुलस फ़ंक्शन फ़ील्ड छलनी
महत्तम सामान्य भाजक	बाइनरी Euclidean विस्तारित यूक्लिडियन लेहमर
मॉड्यूलर वर्गमूल	Cipolla पॉकलिंगटन तनेली -शंक Berlekamp कुनरथ
अन्य एल्गोरिदम	चक्रवाला कॉर्नचिया वर्ग द्वारा घातक पूर्णांक वर्गमूल पूर्णांक संबंध मॉड्यूलर घातांक मोंटगोमरी में कमी शूफ़ ट्रेचेनबर्ग सिस्टम
इटैलिक इंगित करता है कि एल्गोरिथ्म विशेष रूपों की संख्या के लिए है

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 11:57, 10 June 2023

Contents

सिंहावलोकन

उदाहरण

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

स्यूडोकोड

खंडित छलनी

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

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

यूलर की छलनी

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 11:57, 10 June 2023

सिंहावलोकन

उदाहरण

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

स्यूडोकोड

खंडित छलनी

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

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

यूलर की छलनी

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories