Logik !?

[Sven Rautenberg]

Moin!

Eine Mischung erscheint mir ganz sinnvoll:
Man merkt sich die gefundenen Primzahlen.
Und teilt dann nicht mehr durch alle Zahlen von 2 bis sqrt(x), sondern nur durch die gefundenen Primzahlen von 2 bis sqrt(x).
Das reduziert die benötigte Rechenleistung, da nicht mehr sinnlos durch z.B. 4 oder 6 geteilt wird - wenn das ohne Rest möglich wäre, wäre ja schon beim  Teilen durch 2 oder 3 herausgekommen, daß es sich nicht um eine Primzahl handelt.

Klingt gut, ist aber irgendwie nicht umsetzbar.

Entweder lautet die Aufgabe einer Funktion, alle Primzahlen im Intervall von 2 bis x herauszufinden - dann ist ein lineares Abarbeiten des Zahlenbereichst sinnvoll, ebenso das Speichern der Zwischenergebnisse, um diese weiterzuverwenden. Im Prinzip also deine "Mischform" - nur dass diese Mischform eben nichts mischt, sondern das klassische "Sieb" ist.

Oder die Aufgabe lautet, zu einer gegebenen Zahl die Primzahleigenschaft festzustellen. Dann wird man logischerweise von 2 bis sqrt(x) alle Zahlen auf Teilereigenschaft prüfen müssen. Wenn die 2 die Zahl teilt, bricht die Funktion sofort ab, so dass die 4 gar nicht erst geprüft werden muß. Teilt die 2 die zu prüfende Zahl nicht, kommt es sicherlich dazu, dass vielleicht auch mit 4 geprüft wird, was sicherlich unsinnig ist, aber nur verhindert werden könnte, wenn man vorher die Primzahleigenschaft der Zahl 2 festgestellt und daraufhin alle Vielfachen von 2 für die Prüfung gesperrt hätte. Das ist aber doppelt gemoppelt, bzw. wird es hier ziemlich rekursiv: Die Prüfung einer beliebigen Zahl auf Primzahleigenschaft erfordert die Prüfung aller potentieller Teiler auf Primzahleigenschaft, um die Vielfachen der Teiler auszuschließen... da könnte sich die Katze selbst in den Schwanz beißen. Außerdem wäre die Implementation nicht sauber, da die Tabelle, welche Zahlen gesperrt sind, irgendwie zwischen den Funktionsaufrufen weitergereicht werden muß - und das führt dann doch wieder zur Erstellung eines "Siebs".

Allerdings: Eine wirkliche Performance-Verbesserung ist simpel zu realisieren: Als Teiler braucht man im Prinzip nur die 2 zu prüfen und sonst keinerlei geraden Zahlen mehr. Das verdoppelt die Geschwindigkeit grob geschätzt.

- Sven Rautenberg