Sieb von Eratosthenes jenseits von O (n). Beweis

In den Kommentaren zu einem der vorherigen Beiträge über das Sieb von Eratosthenes wurde dieser kurze Algorithmus aus Wikipedia erwähnt:

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

Der Algorithmus ist einfach, aber nicht für alle schien es offensichtlich. Das Hauptproblem ist, dass es auf Wikipedia keine Beweise gibt und der Link zur Quelle ( pdf ) einen anderen Algorithmus als den oben genannten enthält.

In diesem Beitrag werde ich hoffentlich versuchen zu beweisen, dass dieser Algorithmus nicht nur funktioniert, sondern auch für die lineare Komplexität.

Definitionen

$$$\ mathcal {P}$ - viele Primzahlen.
$$$lp (x)$ - minimaler Primteiler einer Zahl: $$$lp (x) = min \ {p \ in \ mathcal {P} \ \ vert \ p \ vert x \}$
$$$rd (x)$ - andere Faktoren: $$$rd (x) = x / lp (x)$

Bitte beachten Sie, dass alle obigen Definitionen für sind $$$x \ ge 2$ .

Einige offensichtliche Eigenschaften der oben eingeführten Funktionen, die später verwendet werden:
$$$lp (a \ mal b) = min (lp (a), lp (b))$
$$$rd (x) <x$
$$$p \ in \ mathcal {P} => lp (p) = p$

Beweis

Lemma 1 : $$$lp (x) \ le lp (rd (x)), \ forall x \ notin \ mathcal {P}, x> 1$
Beweis : Weil jeder Teiler $$$rd (x)$ auch ein Teiler $$$x$ und $$$lp (x)$ keinem Divisor überlegen $$$x$ dann $$$lp (x)$ überschreitet keinen Teiler $$$rd (x)$ einschließlich der kleinsten von ihnen. Das einzige Problem mit dieser Aussage ist wenn $$$rd (x)$ hat keine einfachen Teiler, aber dies ist nur in möglich $$$x \ in \ mathcal {P}$ , was im Zustand des Lemmas ausgeschlossen ist.
$$$\ square$

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

Weil $$$lp (x) \ times rd (x) = x$ (per Definition $$$rd ()$ ), wenn wir viel bekommen hätten $$$E$ dann könnten wir rechnen $$$lp ()$ für alle zusammengesetzten Zahlen bis n. Dies geschieht beispielsweise durch den folgenden Algorithmus:

Algorithmus 2:

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

Beachten Sie das $$$\ vert E \ vert \ le n$ Daher funktioniert der obige Algorithmus 2 für die lineare Komplexität.

Außerdem werde ich beweisen, dass Algorithmus 1 aus Wikipedia tatsächlich nur alle Elemente dieses Satzes durchläuft, da er auf andere Weise parametrisiert werden kann.

Lass $$$E '= \ {(p, r) \ vert p \ in \ mathcal {P}, 2 \ le r <n, p \ le lp (r), p \ mal r \ le n \}$

Lemma 2 : $$$E = E '$
Beweis :

Lass $$$(a, b) \ in E$ => $$$\ existiert x \ notin \ mathcal {P}, \ 2 \ le x \ le n \ mid a = lp (x), b = rd (x)$ .

Per Definition $$$lp (), rd ()$ :: $$$a \ in \ mathcal {P}$ , $$$a \ times b = x$ . Von Lemma 1, $$$a \ le lp (b)$ .
weil $$$rd (x) <x$ dann $$$b <n$ .
Seit $$$x \ notin \ mathcal {P}$ , $$$b \ ge 2$ .
Auch per Definition $$$E$ , $$$x \ le n$ deshalb $$$a \ times b \ le n$ .
Alle 4 Bedingungen $$$E '$ erfüllte Mittel $$$(a, b) \ in E '$ => $$$E \ Teilmenge E '$ .

Lass $$$(a, b) \ in E '$ . Lass $$$x = a \ times b$ .
Per Definition $$$E '$ , $$$a \ in \ mathcal {P}$ . Mittel $$$a$ - einfache Teilung $$$x$ .
$$$lp (x) = lp (a \ mal b) = min (lp (a), lp (b)) = min (a, lp (b)).$
Weil $$$a \ le lp (b)$ dann $$$lp (x) = a.$ Mittel $$$b = rd (x).$
Per Definition $$$x = a \ times b \ le n.$ Auch offensichtlich $$$x = a \ times b \ ge 2.$
Alle Bedingungen für $$$E$ abgeschlossen => $$$E '\ Teilmenge E.$

Deshalb $$$E = E '.$
$$$\ square$

Jetzt bleibt es, die richtigen zu sortieren $$$r$ und $$$p$ aus der Definition der Menge $$$E '$ und wende Algorithmus 2 an. Genau das macht Algorithmus 1 (nur die Variable i wird anstelle von r verwendet). Aber es gibt ein Problem! Alle Elemente einer Menge sortieren $$$E '$ zu berechnen $$$lp,$ wir müssen es wissen $$$lp,$ weil es eine Bedingung in der Definition gibt $$$p \ le lp (r)$ .

Glücklicherweise umgeht dieses Problem die richtige Sortierreihenfolge. Es ist notwendig zu sortieren $$$r$ in der äußeren Schleife und $$$p$ - im Inneren. Dann $$$lp (r)$ wird bereits berechnet. Diese Tatsache wird durch den folgenden Satz bewiesen.

Satz 1:
Algorithmus 1 unterstützt die folgende Invariante: Nach der Iteration der äußeren Schleife für i = k werden alle Primzahlen bis einschließlich k in pr hervorgehoben. Wird auch gezählt $$$lp ()$ für alle $$$x \ notin \ mathcal {P} \ mid x \ le n, \ rd (x) \ le k$ im lp-Array.

Beweis :
Wir beweisen durch Induktion. Für k = 2 wird die Invariante manuell überprüft. Die einzige Primzahl 2 wird zur PR-Liste hinzugefügt, da das Array lp [] anfänglich mit Nullen gefüllt ist. Auch die einzige zusammengesetzte Nummer, in der $$$rd (x) \ le 2$ Ist 4. Es ist leicht zu überprüfen, ob die innere Schleife genau einmal ausgeführt wird (für n> 3) und lp [4] korrekt ausführt: = 2.

Nehmen wir nun an, dass die Invariante für die Iteration i = k-1 gilt. Beweisen wir, dass es auch für die Iteration i = k gilt.

Um dies zu tun, reicht es aus zu überprüfen, ob die Zahl i, wenn sie eine Primzahl ist, zur Liste pr hinzugefügt wird und dass $$$lp ()$ wird für alle zusammengesetzten Zahlen gezählt $$$x \ le n,$ einschließlich $$$rd (x) = i.$ Es sind diese Zahlen aus der Invariante für k, die nicht bereits von der Invariante für k-1 abgedeckt sind.

Wenn i einfach ist, ist lp [i] 0, da die einzige Schreiboperation in das Array lp, die theoretisch lp [i] (in Zeile 6) berechnen könnte, immer in zusammengesetzte Indizes schreibt, weil p * i (für i>) 1) - immer zusammengesetzt. Daher wird die Nummer i zur Liste der Primzahlen hinzugefügt. Außerdem wird in Zeile 3 lp [i] gezählt.

Wenn i zusammengesetzt ist, wird zu Beginn der Iteration lp [i] bereits durch die Invariante für i = k-1 berechnet, weil $$$rd (i) <i$ oder $$$rd (i) \ le i-1,$ Daher fällt ich in der vorherigen Iteration unter die invariante Bedingung. Daher wird die zusammengesetzte Zahl i nicht zur Liste der Primzahlen hinzugefügt.

Wenn das richtige lp [i] und alle Primzahlen bis einschließlich i vorhanden sind, wird die Schleife in den Zeilen 5-6 alle Elemente durchlaufen $$$(p, i) \ in E '$ in dem der zweite Teil ist i:

• $$$p \ in P,$ weil es aus der Liste pr ist
• $$$p \ le lp (i),$ durch Bedingung zum Stoppen des Zyklus
• $$$p \ times i \ le n,$ durch Bedingung zum Stoppen des Zyklus
• $$$i <n,$ folgt aus $$$p \ times i \ le n, \ p> 1$

Alle notwendigen Primzahlen in der PR-Liste sind, weil nur Zahlen bis zu $$$lp (i) \ le i$ . Daher werden lp [] -Werte für alle zusammengesetzten Zahlen berechnet $$$x$ für welche $$$rd (x) = i$ . Dies sind genau alle Zahlen, die beim Übergang von der Invariante für k-1 zur Invariante für k fehlten.

Daher gilt die Invariante für jedes i = 2..n.

$$$\ square$

Durch die Invariante aus Satz 1 für i = n stellt sich heraus, dass alle Primzahlen bis n und alle lp [] durch Algorithmus 1 berechnet werden.

Darüber hinaus werden in den Zeilen 5-6 verschiedene Elemente der Menge sortiert $$$E$ , dann wird die gesamte innere Schleife nicht mehr ausgeführt $$$\ vert E \ vert <n$ Operationen. Die Überprüfungsoperation in der Schleife läuft reibungslos ab $$$\ vert E \ vert + n - 1 <2n$ Zeiten ( $$$\ vert E \ vert$ times gibt true zurück und n-1 times geben für jedes i false zurück. Alle verbleibenden Operationen sind in einem Zyklus in i von 2 bis n verschachtelt.
Daraus folgt, dass die Komplexität von Algorithmus 1 O (n) ist.