Das Kontraxiom
PrimzahlenZusammenfassung: Nachdem ich bei einem firmeninternen Programmierwettbewerb
zum möglichst schnellen Auffinden und Anzeigen der Primzahlen bis
100.000.000 mit Abstand gewonnen hatte und in kürzester Zeit ein
Verfahren - ich taufte es "Kiebart-Kamm" - fand, welches
sich in der Geschwindigkeit gegenüber dem Sieb des Eratosthenes
auszeichnete, beschäftigten mich die Primzahlen weiterhin.
|
|
Im Internet fand ich eine Organisation www.mersenne.org,
die auf der ganzen Welt Computerkapazität suchte, um weitere
Mersenneprimzahlen zu finden. Da die besonders großen Exemplare
für Verschlüsselungsmechanismen wertvoll sind, sind hier auch
Preise von über 100 Tausend Dollar Finderlohn ausgesetzt. So
sind Tausende von Computern auch jetzt, wenn Sie diesen Text
lesen, damit beschäftigt, neue Mersenneprimzahlen zu finden.
Zusammen mit Herrn Willi Jeschke www.primini.de
habe ich mich in die Welt der Primzahlen begeben. Wir fanden
neue Eigenschaften der Primzahlen und arbeiteten uns in immer
tiefer gelegene Sphären der Mathematik ein.
So entstand die Software "Magie der Primzahlen",
die kostenlos im Internet www.euroware.de
herunter geladen werden kann.
Ich beschreibe an dieser Stelle einige Algorithmen, die in dieser
Software verwirklicht wurden.
8 von 30
Bei der Speicherung und der Bearbeitung werden nur die Zahlen
betrachtet, die nicht durch die Faktoren 2, 3 und 5 teilbar
sind. Betrachten wir die Zahlen bis 30 (=2*3*5), so werden nur 8
Zahlen als mögliche Primzahlen erkannt. Es sind dies:
1, 7, 11, 13, 17, 19, 23, 29
Wenn man auf diese 8 Zahlen 30 addiert, erhält man:
31, 37, 41, 43, 47, 49, 53, 59 und wenn man weitere 30er-Vielfache
addiert, sieht man
61, 67, 71, 73, 77, 79, 83, 89
91, 97, 101, 103, 107, 109, 113, 119
121, 127, 131, 133, 137, 139, 143, 149 usw.
Wenn man diese Zahlenfolge fortsetzt, beinhaltet diese alle
möglichen Primzahlen bis auf die ersten drei (2, 3, 5). Einige dieser
Zahlen müssen allerdings noch gestrichen werden, da sie
zusammengesetzt sind.
Zur Speicherung der Primzahlen nutzt man einfacherweise ein Byte
(=8 Bit) zur Darstellung eines 30er Zahlenbereichs. Jedes Bit
entspricht damit einer einzelnen Zahl aus dem eben beschriebenen
Muster.
Nummeriert man die einzelnen Bytes beginnend mit 0, so errechnet
sich die Bedeutung eines einzelnen Bits durch:
Bytenummer * 30 + {1; 7; 11; 13; 17; 19; 23; 29}
Die Primzahlen bis 100 Millionen lassen sich so durch ca. 3,3 MB
Speicher darstellen.
Der Kiebart-Kamm
Der Kiebartkamm beschreibt ein Verfahren, in dem jede Nichtprimzahl
innerhalb der Bitspeicherung genau einmal markiert wird.
Zuerst wird die 1 als Nichtprimzahl markiert. Von nun an gelten
alle Bits als "Nochprimzahlen". Die erste Nochprimzahl wird
mit der zweiten Nochprimzahl multipliziert und das Produkt (im
entsprechenden Bit) als Nichtprim markiert. 7*11 = 77
Mit der 7 werden nun alle Produkte mit Nochprimzahlen gebildet und
als zusammengesetzt (Nichtprim) markiert.
7*13=91
7*17=119
7*19=133
usw. bis zur berechnenden Grenze
Wir fahren fort mit der nächsten Nochprimzahl (11) als Basis für
die Produktbildung und streichen
11*13
11*17
11*19
11*23
usw.
Wir setzen das Verfahren fort mit der Basis 13, 17, 19 usw.
solange, bis die erste Produktbildung einen Wert über die zu bildende
Grenze ergibt. (alternativ solange, wie Basis <= Wurzel aus Grenze)
Wenn wir uns jetzt die verbleibenden Zahlen anschauen, sind dort
nur noch Primzahlen + Quadratzahlen! enthalten.
Um weiterhin jedes Bit nur einmal zu markieren, wird die Wurzel aus
der Grenze berechnet und ab dieser Stelle der Bitspeicher rückwärts
bearbeitet. Zu jeder Nochprimzahl wird das Quadrat gebildet und
gestrichen.
Ein Zählen der Primzahlen innerhalb der vorgegebenen Grenze wird
auf folgendem einfachen Weg möglich:
Summe aller Bits - Markierte Nichtprims + 3 (für die Primzahlen 2,
3, 5)
Während dem Markieren von Nichtprims ist es also ratsam, diese zu
zählen.
Mersenneprimzahlen, Mersennezahlen
siehe eigene Seite hier klicken
|
