Mein Primzahlalgorithmus - Kann sich das wer anschauen?
-
Hier ist erstmal ein Auszug aus der Liste, die ich als Überlegung verwendet habe:
i kleinstmöglicher Teiler (0 = Prim) 01 0 02 0 03 0 04 2 05 0 06 2 07 0 08 2 09 3 10 2 11 0 12 2 13 0 14 2 15 3 16 2 17 0 18 2 19 0 20 2 21 3 22 2 23 0 24 2 25 5 26 2 27 3 28 2 29 0 30 2 31 0 ...
EDIT: Das Muster 2023202 stach mir zuerst ins Auge, bis ich
2020202020202020202020...
0003000003000003000003...
sahDabei bin ich zu Folgendem gekommen:
- Es gibt eine Liste mit "Regeln"
- Jedes Mal, wenn auf eine Zahl keine Regel passt, so ist sie eine Primzahl und
eine Regel wird ergänzt, die zum ersten Mal, bei i² auftritt und dann in regelmäßigen Abständen, solange keine Regel mit kleinerem Abstand vorher greift.
Die Abstände sind:Zahl: 2 3 5 7 11 Abstand: 1 5 9 13 17 = 1+4(n-1) n = 1,2,3,4,...
Die Regel für die Primzahl 2 bedeutet: Die Zahl ist restlos durch 2 teilbar, die für 3: Die Zahl ist restlos durch 3 teilbar...
- Jede Zahl, auf die eine Regel passt, ist keine Primzahl.
-----
Ich bin mir recht sicher, dass das funktioniert, aber ob dies vielleicht schneller ist, als ein anderes Verfahren ist eher fraglich.
Könnte da mal jemand drauf schauen?
Vielleicht ist das auch nur ein anderes Verfahren etwas anders ausgedrückt oder abgewandelt, ich habe micht nicht so damit beschäftigt.
-
Ja, jede dritte Zahl ist durch Drei teilbar und jede zweite von diesen (also insgesamt jede sechste) ist zusätzlich noch durch zwei teilbar, diese Erkenntnis ist nicht ganz neu
. Das klingt wie eine Variante des Siebs des Erastothenes, welches der Standardprimzahlalgorithmus ist, der in Schule und frühen Studiensemestern gelehrt wird, weil er einer der effizienteren Algorithmen unter denjenigen ist, die man noch mit Grundschulmathematik erklären kann.