Das Sieb des Eratosthenes

Weitere Betrachtungen

17.6 Sekunden sind natürlich ein toller Erfolg für ein wenig Nachdenken. Doch wie gut ist das denn? Haben wir schon den „Anschlag“ erreicht?

Überlegen wir, was der Algorithmus - egal in welcher Variante - letztlich leisten muss. Er muss alle Nichtprimzahlen bis n mindestens einmal erzeugen, um sie aus der Liste zu streichen. Davon gibt unterhalb von n = 10⁹ genau 949.152.466 Stück. Wenn wir nun mitzählen, wieviele Produkte i ⋅ k gebildet werden, erhalten wir bei den von uns betrachteten Varianten folgende Werte:

n = 109	Anz. Produkte	Anz. Nichtprimzahlen	Verhältnis
Grundversion	1018	9.49 ⋅ 108	1.1 ⋅ 109
Primzahltabelle_besser_1	9.44 ⋅ 109		9.9
Primzahltabelle_Eratosthenes	2.55 ⋅ 109		2.7
Primzahltabelle_besser_3	9.49 ⋅ 108		1.0

Tatsächlich macht die letzte Variante nicht mehr Arbeit als nötig, sie ist in diesem Sinne optimal!

Interessanterweise bedeutet das aber nicht, dass man den Algorithmus nicht weiter verbessern könnte. Der Vergleich mit den zu streichenden Nichtprimzahlen ist nichts Absolutes, denn man kann die Nichtprimzahlen noch verringern. Das geht mit folgendem Trick: die Tabelle wird nicht mit allen Zahlen ab 2 angelegt, sondern mit der 2 und allen ungeraden Zahlen ab 3. Alle geraden Zahlen ≥ 4 sind sowieso nicht prim, also wozu sie zeitraubend erzeugen? Das Verfahren muss weniger arbeiten auf einer Tabelle, die nur ungerade Primkandidaten enthält, denn die Iteration i = 2 fällt weg. Sie ist die zeitlich längste i-Iteration. Es werden jetzt nur noch folgende Produkte erzeugt:

Diese Idee lässt sich weiter denken: wir verzichten von vornherein auch auf alle echten Vielfachen von 3. Die Tabelle enthält nach der Initialisierung die Zahlen

2

3

5

7

11

13

17

19

23

25

29

31

35

37

41

43

47

49

...

und die Streicharbeit geht mit der Iteration i = 5 los:

Auf diese Weise kann man immer kürzere Tabellen für denselben Zahlenbereich bis n erhalten, indem man die echten Vielfachen von 5, 7, 11, 13, ... weg lässt:

Diese Charakteristik zeigt sich in den Laufzeiten und - da die Tabelle selbst verkleinert wird - den Speichergrößen:

Reduzierung	Laufzeit	Speichergröße
keine	17.6 s	119.2 MByte
ohne 2	33.0 s	59.6 MByte
2, 3	22.6 s	39.7 MByte
2-5	17.8 s	31.8 MByte
2-7	14.7 s	27.3 MByte
2-11	13.3 s	24.8 MByte
2-13	12.6 s	22.9 MByte
2-17	24.0 s	21.6 MByte
2-19	25.9 s	20.4 MByte

Hierbei wurde die fertige Tabelle dargestellt durch ein Array von Bits. An der Stelle i im Array steht 1, wenn i eine Primzahl ist, sonst 0.

Stellt man die Tabelle im Speicher als Liste der Primzahlen dar, so hat man dem gegenüber zwei Nachteile: will man eine bestimmte Zahl auf ihre Primeigenschaft prüfen, muss man erst suchen, ob sie an "ihrem" Platz in der Liste steht. Zum anderen werden die Zahlen bis zu 9-stellig und man braucht für alle 50.847.534 Primzahlen bis 1 Milliarde 1551.7 MByte Speicher.

Dass sich die Laufzeit nach dem Entfernen der geraden Zahlen gegenüber unserem Vorergebnis von 17.6 s fast verdoppelt, liegt daran, dass wir jetzt eine Umrechnung der Tabellenindizes (1,2,3,4,...) auf die jeweils gemeinten Zahlen (im obigen Beispiel: 2,3,5,7,9,...) haben müssen, die etwas Zeit beansprucht. Insgesamt kommen wir jedoch auf ganz hervorragende 12.6 s bei einer reduzierten Tabelle ohne die Vielfachen von 2 bis 13. Danach steigt die Umrechnungsarbeit so stark an, dass sich weitere Reduzierung nicht mehr lohnt.