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

For the sculpture, see The Sieve of Eratosthenes (sculpture).

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

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

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

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

सिंहावलोकन

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

Anonymous

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

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

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

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

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

उदाहरण

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

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

स्यूडोकोड

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

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

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

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

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

खंडित छलनी

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

यूलर की छलनी

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

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

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

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

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

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

यह भी देखें

• प्रिचर्ड की छलनी
• एटकिन की छलनी
• सुंदरम की छलनी
• चलनी सिद्धांत

बाहरी संबंध

• 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.