Zitat:
So ähnlich läuft es ab (kann mich in den Details aber irren).
Du irrst nicht, wobei es denoch eine faszinierende Umschreibung ist
Einfacher gesagt: die Mathemtik die in den verschiednenen Algos. benutzt wird ist eine andere.
Die einfachste Methode ist eine Trial Division mit allen ungeraden Zahlen (und 2) von 2 beginnend bis Wurzel(N). Das Laufzeitverhalten ist das schlechteste aller verfahren und es wächst Quadratisch.
Ein leichte Abwandlung dieses Tests ist mit 6n+-1 zu arbeiten. Das reduziert die Komplexität nur um einen konstanten Faktor, verändert aber nicht deren Progression.
Eine noch bessere Abwandlung benutzt bei dieser Trialdivision nur Primzahlen bis Wurzel(N).
In meinen Algos. verwende ich eine ganz andere Sichtweise:
1.) des mathematiche Verfahren ist im Grunde nicht exakt. D.h. es kann nur 100% exakt erkennen ob eine Zahl X KEINE Primzahl ist, aber wenn es sagt es IST eine Primzahl dann muß dies leider nicht stimmen.
2.) Punkt 1.) wird aber irrelevant weil Andere Leute schon zumindestens alle Zahlen bis 2^32 mit diesem Verfahren überprüft haben und die Parameter für diesen Test verifiziert haben. D.h. mein Verfahren enthält schon unsichtbares Wissen und Informationen. Das wäre so als wenn man extern einmalig mit einem sehr langsammen Test eine tabelle aller Primzahlen erzeugen würde und dann in dere eigenen Anwndung nur noch diese Tabelle implementiert und die zu testende zahl darin nachschlägt.
3.) mein Test besteht im Grunde aus 2 einzelnen und ganz verschiedenen Tests. Als erstes wird eine Testdivision zu allen kleinen Primzahlen bis 137 druchgeführt, und erst danach als zweiter Test der SPP Test.
Wichtig ist aber im Resulat nur die Laufzeit des Verfahrens. Mein Test ist egal mit welcher zahl man arbeitet von der Komplexität her annähernd linear, ist also unabhängig vom Kandidaten den man testen möchte immer gleich schnell.
"Mein Test" ist aber eigentlich nicht von mir, sondern von Mathematikern. Das einzigste was ich geleistet habe ist das ich deren mathematische Grundlagen in ein effizientes Stück Source umgewandelt habe.
Gruß Hagen