Sollte man nicht als erstes mal prüfen, ob die zu prüfende Zahl
- eine gerade Zahl ab 3 (durch 2 teilbar) ist, denn gerade Zahlen sind, abgesehen von der 2, keine Primzahlen;
- durch 3 teilbar ist, denn das erfährt man durch die Ermittlung der Quersumme bis zum Gehtnichtmehr;
- ... und was da noch für schöne mathematische Tricks existieren, die schneller durch sind als das sture Brut-Force-Teilen durch alle kleineren Zahlen?
Obwohl ich kein Mathematiker bin und daher auch nicht das
Primzahlsieb des Eratosthenes kenne, werd' ich mich mal drüber hermachen. Schaun mer mal, ob ich das begreife:
Delphi-Quellcode:
Type
TPrimeTest = Record
Zahl : Integer;
Mark : Byte;
End;
Man macht sich also ein Record-Array vom Typ TPrimeTest, befüllt die Integerwerte mit dem zu testenden Zahlenbereich und setzt die Byte-Werte auf 0 als Marker für
ungetestet:
Dann fängt man an zu sieben, indem man das Array durchiteriert, wobei man gleich mal die ungeraden Vielfachen der aktuellen Zahl, falls vorhanden, mit 1 als Marker für keine Primzahl und natürlich für getestet markiert. Gerade Zahlen, die größer als 3 sind, muß man erst gar nicht aufnehmen, da die sowieso keine Primzahlen sind, weil sie ja alle durch 2 ohne Rest teilbar sind und ihre Vielfachen ebenfalls. Bei 3 blättert man also im Array weiter, bis man auf die 9 stößt, und setzt dessen Bytewert auf 1 (keine Primzahl). Ebenso verfährt man bei der 15 (3x5), der 21 (3x7), 27 (3x9), 33 (3x11) usw. bis zur Maximalzahl, also der Suchgrenze bzw. der Obergrenze des zu durchsuchenden Zahlenbereichs. Vielfache von Geraden kann man sich hier ebenfalls sparen, denn die sind auf jeden Fall auch immer gerade Zahlen und daher keine Primzahlen. Ebenso kann man sich Multiplikatoren sparen, die kleiner sind als die jeweilige Zahl, denn die wurden ebenfalls bereits markiert. Beim zweiten Durchgang hat man dann schonmal viele Zahlen, die Vielfache von kleineren Zahlen sind, als Nicht-Primzahl markiert und muß die nicht mehr prüfen, sondern nur noch die, die den Marker 0 für ungetestet führen. Ebenso verfährt man bei der 5, wo man mit 5x5 beginnt, bei der 7, der 11 (die 9 wurde ja bereits getestet) usw.
Der Satz "Nachdem eine Primzahl gefunden wurde, werden alle Vielfachen dieser Primzahl als zusammengesetzt markiert." leuchtet mir jetzt langsam ein, denn alle Nicht-Primzahlen, die man im weiteren Verlauf des Hochzählens antrifft, wurden ja bereits als Vielfaches einer kleineren Zahl erkannt und markiert. Man kann daher etliches an Rechenzeit sparen, wenn man etwas intelligenteres macht als
brute force.
Ich hab's jetzt nicht getestet, dafür bin ich heute abend schon zu faul und zu müde (wach seit 4:30 Uhr), also lustlos, kein Bock oder was auch immer. Aber etwas ist mir im Wikipedia-Artikel trotzdem noch aufgefallen, dafür reicht's gerade eben noch:
Das Verfahren beginnt also damit, die Vielfachen 4, 6, 8,… der kleinsten Primzahl 2 durchzustreichen. Die nächste unmarkierte Zahl ist die nächstgrößere Primzahl, die 3. Anschließend werden deren Vielfache 9, 12, 15,… durchgestrichen, und so weiter.
Wenn man die geraden Zahlen erst gar nicht ins Array aufnimmt, muß man sie weder prüfen noch "streichen". Das heißt, man muß auch die jeweiligen Vielfachen jener verbliebenen Ungeraden Zahlen, die aus einer Multiplikation mit einer geraden Zahl hervorgehen, nicht prüfen, denn dieses Resultat ist immer eine gerade Zahl und daher niemals eine Primzahl. Zudem kann man auch alle Zahlen, die am Ende eine 5 aufweisen, übergehen, denn die sind alle durch 5 teilbar.
Hat das der
Eratosthenes damals vor 2.285 Jahren nicht bemerkt oder ist der Wikipedia-Artikel diesbezüglich fehlerhaft?