منخل إراتوستينس خارج يا (ن). دليل

في التعليقات على واحدة من المشاركات السابقة حول غربال إراتوستين ، تم ذكر الخوارزمية القصيرة من ويكيبيديا :

الخوارزمية 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. 

الخوارزمية بسيطة ، ولكنها ليست واضحة للجميع. المشكلة الرئيسية هي أنه لا يوجد دليل على ويكيبيديا ، وأن الرابط إلى المصدر ( pdf ) يحتوي على خوارزمية مختلفة إلى حد ما عما سبق.

آمل أن أتمكن في هذا المنشور من إثبات أن هذه الخوارزمية لا تعمل فحسب ، بل تعمل أيضًا من أجل التعقيد الخطي.

حدد

$$$\ mathcal {P}$ - الكثير من الأعداد الأولية.
$$$lp (x)$ - الحد الأدنى للقسمة الأولية لعدد: $$$lp (x) = دقيقة \ {p \ in \ mathcal {P} \ \ vert \ p \ vert x \}$
$$$rd (x)$ - عوامل أخرى: $$$rd (x) = x / lp (x)$

يرجى ملاحظة أن جميع التعاريف المذكورة أعلاه هي ل $$$x \ ge 2$ .

بعض الخصائص الواضحة للوظائف المقدمة أعلاه ، والتي سيتم استخدامها لاحقًا:
$$$lp (a \ times 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$ و $$$lp (x)$ ليست متفوقة على أي المقسوم عليها $$$x$ ثم $$$lp (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) \ times rd (x) = x$ (بحكم التعريف $$$rd ()$ ) ، إذا تلقينا الكثير $$$E$ ثم يمكننا حساب $$$lp ()$ لجميع الأرقام المركبة تصل إلى ن. يتم ذلك ، على سبيل المثال ، بواسطة الخوارزمية التالية:

الخوارزمية 2:

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

لاحظ ذلك $$$\ vert E \ vert \ le n$ لذلك الخوارزمية 2 أعلاه تعمل من أجل تعقيد خطي.

علاوة على ذلك ، سأثبت أن الخوارزمية 1 من ويكيبيديا تتكرر فعليًا على جميع عناصر هذه المجموعة ، لأنه يمكن تحديدها بطريقة مختلفة.

سمح $$$E '= \ {(p، r) \ vert p \ in \ mathcal {P} ، 2 \ le r <n ، p \ le lp (r) ، p \ times r \ le n \}$

ليما 2 : $$$E = E '$
دليل :

سمح $$$(a، b) \ in E$ => $$$\ موجود x \ notin \ mathcal {P} ، \ 2 \ le x \ le n \ mid a = lp (x) ، b = rd (x)$ .

بحكم التعريف $$$lp () ، rd ()$ : $$$a \ in \ mathcal {P}$ . $$$a \ times b = x$ . بواسطة Lemma 1 ، $$$a \ le lp (b)$ .
ل $$$rd (x) <x$ ثم $$$b <n$ .
كما $$$x \ notin \ mathcal {P}$ . $$$ب \ جنرال الكتريك 2 دولا$ .
أيضا ، بحكم التعريف $$$E$ . $$$x \ le n$ من هنا $$$a \ times b \ le n$ .
كل 4 شروط $$$E '$ الوفاء بالوسائل $$$(a، b) \ in E '$ => $$$E \ subset E '$ .

سمح $$$(a، b) \ in E '$ . سمح $$$x = a \ times b$ .
بحكم التعريف $$$E '$ . $$$a \ in \ mathcal {P}$ . وبالتالي، $$$دولا$ - الفجوة البسيطة $$$x$ .
$$$lp (x) = lp (a \ times b) = min (lp (a) ، lp (b)) = min (a، lp (b)).$
المعارف التقليدية $$$a \ le lp (b)$ ثم $$$lp (x) = a.$ وبالتالي، $$$b = rd (x).$
بحكم التعريف ، $$$x = a \ times b \ le n.$ من الواضح أيضا $$$x = a \ times b \ ge 2.$
جميع الظروف ل $$$E$ اكتمل => $$$E '\ subset E.$

لذلك، $$$E = E '.$
$$$\ مربع$

الآن يبقى فرز تلك الصحيحة $$$ص$ و $$$ع$ من تعريف المجموعة $$$E '$ وتطبيق الخوارزمية 2. هذا هو بالضبط ما تفعله الخوارزمية 1 (يتم استخدام المتغير i فقط بدلاً من r). لكن هناك مشكلة! للفرز من خلال جميع عناصر مجموعة $$$E '$ لحساب $$$lp ،$ نحن بحاجة إلى معرفة $$$lp ،$ لأن هناك شرط في التعريف $$$p \ le lp (r)$ .

لحسن الحظ ، هذه المشكلة تدور حول ترتيب الفرز الصحيح. من الضروري الفرز $$$ص$ في الحلقة الخارجية ، و $$$ع$ - في الداخل. ثم $$$lp (r)$ سيتم بالفعل حسابها. هذه الحقيقة أثبتتها النظرية التالية.

نظرية 1:
الخوارزمية 1 تدعم الثابت التالي: بعد التكرار للحلقة الخارجية لـ i = k ، سيتم إبراز جميع الأعداد الأولية حتى k ضمناً في pr. سوف تحسب أيضا $$$lp ()$ للجميع $$$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 و ذلك $$$lp ()$ سيتم حسابها لجميع الأرقام المركبة $$$x \ le n،$ بما في ذلك $$$rd (x) = i.$ هذه الأرقام من الثابت لـ k غير المشمولة بالفعل من قبل الثابت لـ k-1.

إذا كنت بسيطًا ، فسيكون lp [i] صفرًا ، لأن عملية الكتابة الوحيدة إلى الصفيف lp ، والتي من الناحية النظرية يمكنها حساب lp [i] (على السطر 6) ، تكتب دائمًا إلى مؤشرات مركبة ، لأن p * i (لـ i> 1) - دائما مركب. لذلك ، سيتم إضافة الرقم i إلى قائمة الأعداد الأولية. أيضًا ، في السطر 3 ، سيتم حساب lp [i].

إذا كنت مركبًا ، فسيتم حساب بداية التكرار lp [i] بالفعل من قبل الثابت لـ i = k-1 ، لأن $$$rd (i) <i$ أو $$$rd (i) \ le i-1،$ لذلك ، أنا يقع تحت الشرط الثابت في التكرار السابق. لذلك ، لن يتم إضافة الرقم المركب إلى قائمة الأعداد الأولية.

علاوة على ذلك ، بوجود lp [i] الصحيح وجميع الأعداد الأولية حتى i inclusive ، ستكرر الحلقة في الأسطر 5-6 على جميع العناصر $$$(p ، i) \ in E '$ حيث الجزء الثاني هو:

• $$$p \ in P ،$ لأنه من القائمة العلاقات العامة
• $$$p \ le lp (i)،$ بشرط لإيقاف الدورة
• $$$p \ times i \ le n،$ بشرط لإيقاف الدورة
• $$$i <n،$ يتبع من $$$p \ times i \ le n، \ p> 1$

جميع الأعداد الأولية اللازمة في قائمة العلاقات العامة هي ، لأن فقط أرقام تصل إلى $$$lp (i) \ le i$ . لذلك ، سيتم حساب قيم lp [] لجميع الأرقام المركبة $$$x$ من اجل ذلك $$$rd (x) = i$ . هذه هي بالضبط جميع الأرقام التي كانت مفقودة أثناء الانتقال من الثابت ل k-1 إلى الثابت ل k.

لذلك ، يحمل ثابت لأي i = 2..n.

$$$\ مربع$

بواسطة الثابت من Theorem 1 لـ i = n اتضح أن جميع الأعداد الأولية تصل إلى n وأن كل lp [] سيتم حسابها بواسطة الخوارزمية 1.

وعلاوة على ذلك ، لأنه في الصفوف 5-6 يتم فرز عناصر مختلفة من المجموعة $$$E$ ، ثم سيتم تنفيذ الحلقة الداخلية الإجمالية لا أكثر $$$\ vert E \ vert <n$ العمليات. سيتم تشغيل عملية الفحص في الحلقة بسلاسة $$$\ vert E \ vert + n - 1 <2n$ مرات ( $$$\ vert E \ vert$ ستعود مرات حقيقية و n-1 مرات ، لكل i ، ستعود خاطئة). جميع العمليات المتبقية متداخلة في دورة واحدة في i من 2 إلى n.
ويترتب على ذلك أن تعقيد الخوارزمية 1 هو O (n).