सुंदरम छलनी

नेटवर्क में सुंदरमा छलनी को संक्षिप्त पृष्ठभूमि जानकारी के स्रोतों की एक बड़ी संख्या द्वारा दर्शाया गया है। फिर भी, मैंने यह बताने का निर्णय लिया कि मैं खुद क्या संख्या-सिद्धांतवादी एल्गोरिदम के अध्ययन की शुरुआत में पढ़ना चाहूंगा।

सुन्दरम छलनी प्राइम नंबर उत्पन्न करने के तीन सबसे प्रसिद्ध तरीकों में से एक है। अब यह खराब कम्प्यूटेशनल जटिलता के कारण कुछ विदेशी के रूप में व्यवहार करने के लिए प्रथागत है: ओ (एन (logN))। हालाँकि, asymptotics asymptotics हैं, और व्यवहार में, 32-बिट sieving रेंज में, Atkin, उदाहरण के लिए, सुंदरम को केवल सावधानीपूर्वक अनुकूलन से आगे निकल जाता है।

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

सुंदरामा छलनी सभी संख्याओं को प्राकृतिक संख्या 3 ≤ n s N "घटकों के बाहर" जाने में पाती है। व्यापकता के नुकसान के बिना, एन के मूल्य को विषम माना जा सकता है। यदि एन भी है, तो यह समग्र होने की गारंटी है, और इसे ऊपरी सीमा के मूल्य को एक से कम करके साइडिंग रेंज से बाहर रखा जा सकता है।

एल्गोरिथ्म निम्नलिखित तथ्य पर आधारित है। किसी भी विषम समग्र संख्या n को एक से अधिक दो प्राकृतिक विषम संख्याओं के उत्पाद के रूप में दर्शाया जा सकता है:

(1) n = (2 * i + 1) * (2 * j + 1),

जहाँ i और j प्राकृतिक संख्याएँ हैं (शून्य कोई प्राकृतिक संख्या नहीं है)। इस रूप में एक अभाज्य संख्या n की कल्पना करना असंभव है, अन्यथा इसका मतलब यह होगा कि n में स्वयं और एक के अलावा अतिरिक्त विभाजक हैं।

हम 2 * m + 1 के रूप में विषम n लिखते हैं, इसे (1) में प्रतिस्थापित करते हैं, और m के लिए अभिव्यक्ति प्राप्त करते हैं:

(२) म = २ * मैं * जे + आई + जे।

यह परिवर्तन सीधे सुंदरम की छलनी का विचार करता है।

दिए गए अंतराल से संयुक्त संख्याओं को बाहर निकालने के लिए, आपको एक सरणी का उपयोग करना चाहिए जिसमें सूचकांक m वाला तत्व 2 * m + 1 का प्रतिनिधि है। चर i और j के मानों की गणना आयोजित करने के बाद, हम सूत्र (2) द्वारा सूचकांक m की गणना करेंगे, और इसी में। सरणी तत्वों ने "समग्र संख्या" चिह्न सेट किया। गणना पूरा होने के बाद, रेंज में सभी मिश्रित संख्याओं को चिह्नित किया जाएगा, और निशान की अनुपस्थिति से primes का चयन किया जा सकता है।

यह तकनीकी विवरणों को स्पष्ट करने के लिए बना हुआ है।

पिछली तर्क के आधार पर, sieving रेंज एन की ऊपरी (विषम) सीमा का प्रतिनिधित्व करने के लिए, सूचकांक एम अपने अधिकतम मूल्य mmax = (एन - 1) / 2 मानता है। यह सरणी का आवश्यक आकार निर्धारित करता है।

हम दो चक्रों में i और j के मूल्यों की गणना करेंगे: i के मूल्यों की गणना के लिए एक बाहरी लूप, और j के मूल्यों के लिए एक नेस्टेड आंतरिक लूप।

बाहरी लूप काउंटर का प्रारंभिक मान i = 1 है। दोहराए गए दोहराए गए गणना से बचने के लिए, चर i और j की अभिव्यक्ति की पूर्ण समरूपता (2) को देखते हुए, आंतरिक चक्र मान j = i से शुरू होना चाहिए।

बाहरी लूप काउंटर इमैक्स। I के लिए अधिकतम मान ज्ञात करें। यदि रेंज N की सीमा एक विषम संयुक्त संख्या है, तो i = imax के मान के साथ, आंतरिक लूप को कम से कम एक बार इसके पैरामीटर j = imax के मान से निष्पादित किया जाना चाहिए, और अभिव्यक्ति (2) इसका अधिकतम मूल्य लेगा।

एममेक्स = 2 * इमैक्स * इमैक्स + इमैक्स + इमैक्स,
imax ^ 2 + इमैक्स - एममैक्स / 2 = 0।

इस द्विघात समीकरण को हल करते हुए, हम प्राप्त करते हैं: imax = (2 (2 * mmax + 1) -1) / 2 = (2N-1) / 2।
आंतरिक चक्र jmax found j के काउंटर के लिए प्रतिबंध असमानता से पाया जाता है
एममेक्स, 2 * i * j + i + j , जहाँ हमें मिलता है: jmax = (mmax - i) / (2 * i + 1)।

ऊपरी सीमा के मूल्यों को भिन्नात्मक भाग को छोड़ते हुए, पूरे पूरे मूल्य पर गोल किया जाना चाहिए।

निम्नलिखित एक बहुत ही सरल सी # सुंदरम वर्ग की एक सूची है जो वर्णित विधि को लागू करता है।

using System; using System.Collections; namespace CSh_Sundaram { public class Sundaram { public double dt; //   () private long t1; //   private long t2; //   private uint limit; //     private int arrlength; //   private BitArray Prim; //    private int counter; public Sundaram(uint _limit) { limit = _limit; if (limit % 2 == 0) limit -= 1; arrlength = (int)(limit / 2); Prim = new BitArray(arrlength); t1 = DateTime.Now.Ticks; Sieve(); //  t2 = DateTime.Now.Ticks; dt = (double)(t2 - t1) / 10000000D; counter = -1; } public uint NextPrime { get { while (counter < arrlength - 1) { counter++; if (!Prim[counter]) return (uint)(2 * counter + 3); } return 0; } } private void Sieve() { int imax = ((int)Math.Sqrt(limit) - 1) / 2; for (int i = 1; i <= imax; i++) { int jmax = (arrlength - i) / (2 * i + 1); for (int j = i; j <= jmax; j++) { Prim[2 * i * j + i + j - 1] = true; } } } } } 

एक पैरामीटर के रूप में जब सुंदरम का प्रकार बनाते हैं, तो सीमा रेंज की ऊपरी सीमा का संकेत दिया जाता है। शिफ्टिंग के लिए, क्लास BitArray प्रकार की एक सरणी का उपयोग करता है। यह रनटाइम बढ़ाता है, लेकिन आपको यूंट प्रकार की पूरी 32-बिट रेंज को कवर करने की अनुमति देता है। वर्ग रचनाकार से छलनी () विधि तक पहुंचते समय स्थानांतरण किया जाता है। इसके पूरा होने के बाद, dt फ़ील्ड में सेकंड में छलनी का निष्पादन समय होगा।

नेक्स्टप्राइम प्रॉपर्टी को एक्सेस करते समय, क्रमिक रूप से, 3 से शुरू होकर, आरोही क्रम में, प्राइम्स वापस आ जाएंगे। सीमा से सभी सरल समाप्त होने के बाद, मान 0 वापस कर दिया जाएगा।