हे (एन) से परे एराटोस्थनीज की छलनी। सबूत

एराटोस्थनीज की छलनी के बारे में पिछले पोस्टों में से एक में, विकिपीडिया से इस लघु एल्गोरिथ्म का उल्लेख किया गया था:

एल्गोरिथम 1:

1:  i := 2, 3, 4, ...,  n: 2:  lp[i] = 0: 3: lp[i] := i 4: pr[] += {i} 5:  p  pr  p ≤ lp[i]  p*i ≤ n: 6: lp[p*i] := p : lp -        n pr -     n. 

एल्गोरिथ्म सरल है, लेकिन हर किसी के लिए यह स्पष्ट नहीं लग रहा था। मुख्य समस्या यह है कि विकिपीडिया पर कोई सबूत नहीं है, और स्रोत ( पीडीएफ ) के लिंक में ऊपर से एक अलग एल्गोरिथ्म शामिल है।

इस पोस्ट में मैं कोशिश करूँगा, मुझे उम्मीद है, यह साबित करना संभव है कि यह एल्गोरिथम न केवल काम करता है, बल्कि यह रैखिक जटिलता के लिए भी करता है।

परिभाषित

$$$\ mathcal {P}$ - बहुत सारे अपराध।
$$$एलपी (एक्स)$ - किसी संख्या का न्यूनतम प्रमुख भाजक: $$$lp (x) = min \ {p \ in \ mathcal {P} \ \ vert \ p \ vert x \ "$
$$$rd (x)$ - अन्य कारक: $$$rd (x) = x / lp (x)$

कृपया ध्यान दें कि उपरोक्त सभी परिभाषाएँ हैं $$$x \ ge 2$ ।

ऊपर पेश किए गए कार्यों के कुछ स्पष्ट गुण, जो बाद में उपयोग किए जाएंगे:
$$$lp (a \ टाइम्स b) = min (lp (a), lp (b))$
$$$rd (x) <x$
$$$p \ in \ mathcal {P} => lp (p) = p$

सबूत

लेम्मा 1 : $$$lp (x) \ le lp (rd (x)), \ forall x \ notin \ mathcal {P}, x> 1$
प्रमाण : क्योंकि कोई भी भाजक $$$rd (x)$ एक विभक्त भी $$$x$ , और $$$एलपी (एक्स)$ किसी भी भाजक से श्रेष्ठ नहीं $$$x$ तो $$$एलपी (एक्स)$ किसी भी भाजक से अधिक नहीं है $$$rd (x)$ उनमें से सबसे छोटा भी शामिल है। इस कथन के साथ एकमात्र समस्या है अगर $$$rd (x)$ सरल विभाजक नहीं है, लेकिन यह केवल तभी संभव है जब $$$x \ in \ mathcal {P}$ , जो लेम्मा की स्थिति में बाहर रखा गया है।
$$$\ वर्ग$

चलो $$$E = \ {(lp (x), rd (x)) \ vert \ forall x \ notin \ mathcal {P}, 2 \ le x \ le n \}$

क्योंकि $$$lp (x) \ टाइम्स rd (x) = x$ (परिभाषा के अनुसार $$$rd ()$ ), अगर हमें बहुत कुछ दिया गया $$$ई$ तब हम गणना कर सकते थे $$$एलपी ()$ सभी समग्र संख्याओं के लिए n तक। यह, उदाहरण के लिए, निम्नलिखित एल्गोरिथम द्वारा किया जाता है:

एल्गोरिथम 2:

 1:   (l,r)  E: 2: lp[l*r] := l; 

ध्यान दें $$$\ $ इसलिए एल्गोरिथम 2 ऊपर रैखिक जटिलता के लिए काम करता है।

इसके अलावा, मैं यह साबित कर दूंगा कि विकिपीडिया से एल्गोरिथम 1 वास्तव में इस सेट के सभी तत्वों पर आधारित है, क्योंकि इसे एक अलग तरीके से परिचालित किया जा सकता है।

चलो $$$E '= \ {(p, r) \ vert p \ in \ mathcal {P}, 2 \ le r <n, p \ le lp (r), p \ टाइम्स r \ le n \}$

लेम्मा 2 : $$$ई = ई ’$
प्रमाण :

चलो $$$(ए, बी) ई $ मे$ => $$$\ मौजूद है x \ notin \ mathcal {P}, \ 2 \ le x \ le n \ mid a = lp (x), b = rd (x)$ ।

परिभाषा से $$$एलपी (), आरडी ()$ : $$$a \ in \ mathcal {P}$ । $$$a_ बार b = x$ । लेम्मा 1 द्वारा, $$$a \ le lp (b)$ ।
क्योंकि $$$rd (x) <x$ तो $$$b <n$ ।
जैसे $$$x \ notin \ mathcal {P}$ । $$$b \ ge 2$ ।
इसके अलावा, परिभाषा के अनुसार $$$ई$ । $$$x \ le n$ इसलिये $$$a \ b b \ le n$ ।
सभी 4 स्थितियां $$$ई ’$ पूर्ण साधन $$$(ए, बी) \ ई में$ => $$$E \ सब्सेट E '$ ।

चलो $$$(ए, बी) \ ई में$ । चलो $$$x = a \ b b$ ।
परिभाषा से $$$ई ’$ । $$$a \ in \ mathcal {P}$ । इसलिए, $$$एक$ - सरल विभाजन $$$x$ ।
$$$lp (x) = lp (a \ टाइम्स b) = min (lp (a), lp (b)) = min (a, lp (b)) $$
TK $$$a \ le lp (b)$ तो $$$lp (x) = a$ इसलिए, $$$b = rd (x)$
परिभाषा के अनुसार, $$$x = a \ टाइम्स b \ le n।$ स्पष्ट रूप से भी $$$x = a \ टाइम्स b \ ge 2.$
के लिए सभी शर्तें $$$ई$ पूरा => $$$E '\ subset E.$

इसलिए, $$$ई = ई ’$
$$$\ वर्ग$

अब यह सही लोगों को छाँटने के लिए है $$$आर$ और $$$पी$ सेट की परिभाषा से $$$ई ’$ और एल्गोरिथ्म 2 को लागू करें। यह ठीक वैसा ही है जैसा कि अल्गोरिथम 1 करता है (केवल i चर का उपयोग r के बजाय किया जाता है)। लेकिन एक समस्या है! एक सेट के सभी तत्वों के माध्यम से सॉर्ट करने के लिए $$$ई ’$ गणना करना $$$एलपी,$ हमें जानने की जरूरत है $$$एलपी,$ क्योंकि परिभाषा में एक शर्त है $$$p \ le lp (r)$ ।

सौभाग्य से, यह समस्या सही क्रमबद्ध क्रम के आसपास हो जाती है। इसे छांटना जरूरी है $$$आर$ बाहरी लूप में, और $$$पी$ - अंदर में। तो $$$एलपी (आर)$ पहले से ही गणना की जाएगी। यह तथ्य निम्नलिखित प्रमेय द्वारा सिद्ध होता है।

प्रमेय 1:
एल्गोरिथ्म 1 निम्नलिखित इनवेरिएंट का समर्थन करता है: i = k के लिए बाहरी लूप के पुनरावृत्ति के बाद, k के लिए सभी primes को मुख्य रूप से हाइलाइट किया जाएगा। भी गिना जाएगा $$$एलपी ()$ सभी के लिए $$$x \ notin \ mathcal {P} \ mid x \ le n, \ rd (x) \ le k$ एलपी सरणी में।

प्रमाण :
हम प्रेरण द्वारा साबित होते हैं। K = 2 के लिए, इन्वर्टर को मैन्युअल रूप से जांचा जाता है। केवल मुख्य 2 को पीआर सूची में जोड़ा जाएगा, क्योंकि lp [] सरणी शुरू में शून्य से भर जाती है। साथ ही, एकमात्र यौगिक संख्या जिसमें $$$rd (x) \ le 2$ - यह 4. यह सत्यापित करना आसान है कि आंतरिक लूप एक बार (n> 3 के लिए) निष्पादित करेगा और सही ढंग से lp [4]: ​​= 2 को निष्पादित करेगा।

अब मान लीजिए कि आक्रमणकारी पुनरावृत्ति i = k-1 के लिए रखता है। आइए हम यह साबित करें कि यह पुनरावृत्ति i = k के लिए भी मान्य होगा।

ऐसा करने के लिए, यह जांचने के लिए पर्याप्त है कि संख्या i, यदि यह अभाज्य है, सूची pr और उस में जोड़ी जाएगी $$$एलपी ()$ सभी समग्र संख्याओं के लिए गिना जाएगा $$$x \ le n,$ सहित $$$rd (x) = i$ यह k के लिए इनवेरिएंट से ये संख्याएं हैं जो पहले से ही k-1 के लिए इनवेरिएंट द्वारा कवर नहीं किए गए हैं।

यदि मैं सरल हूं, तो lp [i] 0 होगा, क्योंकि सरणी lp पर एकमात्र लिखने वाला ऑपरेशन, जो सैद्धांतिक रूप से lp [i] (6 लाइन पर) की गणना कर सकता है, हमेशा समग्र सूचकांकों को लिखता है, क्योंकि p * i (i के लिए) 1) - हमेशा यौगिक। इसलिए, मैं primes की सूची में संख्या जोड़ दी जाएगी। इसके अलावा, लाइन 3 में, lp [i] को गिना जाएगा।

यदि मैं संमिश्र है, तो पुनरावृति lp की शुरुआत में [i] पहले से ही i = k-1 के लिए आवधिक द्वारा गणना की जाएगी, क्योंकि $$$rd (i) <i$ या $$$rd (i) \ le i-1,$ इसलिए, मैं पिछले पुनरावृत्ति में अपरिवर्तनीय स्थिति में आता हूं। इसलिए, primes की सूची में समग्र संख्या i को नहीं जोड़ा जाएगा।

इसके अलावा, सही lp [i] होने और i समावेशी तक सभी primes, 5-6 लाइनों में लूप सभी तत्वों को पुनरावृत्त कर देगा $$$(p, i) \ E में$ जिसमें दूसरा भाग i:

• $$$पी में पी,$ क्योंकि यह सूची जनसंपर्क से है
• $$$p \ le lp (i),$ चक्र को रोकने के लिए शर्त के द्वारा
• $$$p \ गुना i \ le n,$ चक्र को रोकने के लिए शर्त के द्वारा
• $$$i <n,$ इस प्रकार है $$$p \ गुना i \ le n, \ p> 1$

जनसंपर्क सूची में सभी आवश्यक primes हैं, क्योंकि केवल संख्या तक $$$lp (i) \ le i$ । इसलिए, एलपी [] मूल्यों की गणना सभी मिश्रित संख्याओं के लिए की जाएगी $$$x$ जिसके लिए $$$rd (x) = i$ । ये ठीक वे सभी संख्याएँ हैं जो k-1 के लिए invariant से k के लिए invariant से संक्रमण के दौरान गायब थीं।

इसलिए, आक्रमणकारी किसी भी i = 2. एन के लिए रखता है।

$$$\ वर्ग$

1 = i = n के लिए प्रमेय 1 से हमलावर द्वारा यह पता चला है कि सभी pr तक n और सभी lp [] की गणना एल्गोरिथ्म 1 द्वारा की जाएगी।

इसके अलावा, चूंकि पंक्तियों में 5-6 सेट के विभिन्न तत्वों को क्रमबद्ध किया गया है $$$ई$ , तो कुल आंतरिक लूप कोई और अधिक निष्पादित करेगा $$$\ vert E \ vert <n$ संचालन। लूप में चेक ऑपरेशन आसानी से चलेगा $$$\ ऊर्ध्वाधर E \ vert + n - 1 <2n$ समय ( $$$\ ऊर्ध्वाधर E \ vert$ समय सही और n-1 बार आएगा, प्रत्येक i के लिए, गलत वापस आएगा)। शेष सभी ऑपरेशनों को i से 2 से n में एक चक्र में नेस्ट किया जाता है।
यह निम्नानुसार है कि एल्गोरिथ्म 1 की जटिलता ओ (एन) है।