Als willkommenen Nebeneffekt können wir auch den Laufbereich für i begrenzen. Aus den beiden Einschränkungen i ≤ k ≤ n/i erhalten wir i² ≤ n, also i ≤ √n. Für höhere i ist der k-Bereich leer.
Der Algorithmus hat bis hierher das folgende Aussehen bekommen:

(Das Zeichen ⌊&sdot⌋ bedeutet Abrundung, denn i und k können nur ganzzahlige Werte annehmen.)
Wie schnell sind wir jetzt geworden? Die neuen Laufzeiten:

Der Effekt ist recht spürbar, denn das Ziel 10⁹ ist schon in Reichweite: nur noch siebeneinhalb Minuten entfernt. Lassen wir den Computer in Gedanken laufen und nutzen diese Zeit, um es vielleicht noch besser zu machen!

Brauchen wir jeden i-Wert?

Schauen wir an, was innerhalb der i-Schleife (Zeile 2) genau passiert: i bleibt fest und k durchläuft seine Schleife (Zeile 3). Dabei erhält das Produkt i ⋅ k die Werte

Ob nun i eine Primzahl ist oder nicht, könnte uns die Liste selbst sagen - wenn sie schon fertig wäre. Wir können aber erst nach dem Ende des Algorithmus sicher sein, dass nur noch Primzahlen in der Liste stehen. Oder?
Ja und nein. Im allgemeinen Ja, denn sonst könnten wir den Algorithmus abkürzen. Das ist nicht immer der Fall, nehmen wir zum Beispiel n = 100 : die Nichtprimzahl 91 muss irgendwann aus der Liste gestrichen werden. Sie wird aber erst ganz kurz vor dem Ende erzeugt, nämlich für i = 7, k = 13.
In unserem speziellen Fall aber Nein, denn wir wollen ja nicht jede beliebige Zahl als Primzahl erkennen, sondern eine ganz bestimmte, die Zahl i. Und das auch nicht zu beliebiger Zeit, sondern erst zum Anfang der k-Schleife für den Wert i. Hier gibt uns die Liste eine korrekte Auskunft! Warum?
Wir hatten oben beobachtet, dass für jedes feste i alle gestrichenen Werte i ⋅ k ≥ i² sind. Anders ausgedrückt: im Zahlenbereich 2, ..., i² - 1 wird nichts verändert. Da i im weiteren Verlauf nur steigt, wächst auch dieser Bereich und enthält alle Bereiche vor ihm. Im folgenden Bild sind diese Bereiche blau dargestellt:

Da innnerhalb dieser Bereiche bis zum Ende des Algorithmus keine Veränderungen mehr auftreten, müssen sie bereits vor dem Durchlauf der k-Schleife für das jeweilige i korrekt sein. Die Tabelle wird sozusagen in quadratischen Sprüngen fertig. Grün eingezeichnet ist der Wert i selbst, den wir auf seine Primeigenschaft prüfen wollen. Es ist gut zu erkennen, dass er immer in einem blauen Bereich liegt. Um zu entscheiden, ob i eine Primzahl ist, dürfen wir also einfach in der aktuellen Liste nachschauen.
Wir können im Algorithmus die i-Schleife jetzt wie folgt ergänzen:

Diese Version des Verfahrens hatte der kluge Grieche vorgestellt und es heißt nach seinem Erfinder das Sieb des Eratosthenes. Sieb deswegen, weil es die gewünschten Objekte, die Primzahlen, nicht gezielt konstruiert, sondern im Gegenteil alle Nichtprimzahlen aussondert.

Unsere Zeitmessung sagt zu seinem Algorithmus:

Bei n=10⁹ nur noch gut eine Minute!

Geht es noch schneller?

Mit einem ähnlichen Argument wie für die i-Werte können wir auch die Werte der k-Schleife weiter einschränken: wir brauchen nur diejenigen zu betrachten, die in der Liste gefunden werden. Steht k nämlich nicht mehr dort, ist k als Nichtprimzahl gestrichen worden und besitzt einen Primteiler p < k. Im Durchgang der i-Schleife mit i = p wurden alle Vielfachen von p gestrichen, insbesondere k und seine Vielfachen. Es ist an dieser Stelle nichts mehr zu tun.
Es wäre nun nahe liegend, den Algorithmus wie folgt zu ergänzen:

Doch Achtung! Diese Formulierung hat ihre Tücken. Lassen wir den Algorithmus so laufen, erzeugt er die folgende Tabelle:

Was läuft falsch? Sehen wir uns die ersten Schritte des Algorithmus genau an. Nach der Initialisierung der Liste mit allen Zahlen bis n (Zeile 1) steht darin:

Zunächst wird i = 2 gesetzt und dann k = 2 . Die 2 steht in der Liste, also wird i ⋅ k = 4 gestrichen:

Im nächsten Schritt ist k = 3 . Die 3 steht ebenfalls in der Liste und so wird i ⋅ k = 6 gestrichen:

Jetzt passiert′s: k = 4 steht nicht mehr in der Liste, denn sie wurde ja als erste gestrichen. Entsprechend wird für k = 4 wegen der neuen Bedingung nichts gemacht und der Algorithmus fährt mit k = 5 fort:

So bleibt 2 ⋅ 4 = 8 irrtümlich in der Liste stehen. Das Problem ist, dass k beim Schleifendurchlauf stets größere Zahlen i ⋅ k > k streicht und dann selbst erhöht wird. Irgendwann bekommt k den Wert eines vormaligen Produktes i ⋅ k und das Verfahren wirkt ungünstig auf sich selbst zurück:

Die Lösung besteht darin, k seinen Schleifenbereich rückwärts durchlaufen zu lassen. Dadurch wird diese Rückwirkung vermieden:

Mit dieser Überlegung werden nur noch die folgenden Produkte i ⋅ k gebildet:

Insgesamt ergibt sich nun die folgende Version des Algorithmus:

Seine Laufzeiten:

Dieses Ergebnis ist für heutige Standards durchaus akzeptabel. Wir haben ausgehend von der naiven Grundversion mit wenigen gezielten Überlegungen den Algorithmus für n = 10⁹ um den Faktor 254.5 Millionen beschleunigt!

Im nachfolgenden Applet könnt ihr euch für verschiedene Werte von n anschauen, welche Werte für i, k und i ⋅ k der Algorithmus in seinen Varianten durchläuft. (Erwartet die guten Rechenzeiten nicht von dem Applet. Mehr als n = 10⁴ schafft es nicht.)

Was können wir aus diesem Beispiel lernen?

• Einfache Rechenverfahren sind nicht automatisch effizient,
• zu ihrer Beschleunigung muss man sie gut verstehen,
• es sind oft viele Verbesserungen möglich,
• mathematische Ideen können sehr weitreichend sein!