Primzahlen berechnen
Alle Primzahlen bis zu einer Grenze
Aus einer Liste aller ganzen Zahlen von 2 bis zur Grenze streichen wir zuerst alle Vielfachen von 2 (also 4, 6, 8, ...), dann von 3, dann von der nächsten noch nicht gestrichenen Zahl usw. (Sieb des Eratosthenes oder effizienter: Sieb von Atkin).
Dieses Verfahren ist am schnellsten, um eine Liste von Primzahlen zu erstellen. (Du kannst dir die ersten 50 Millionen Primzahlen aber auch einfach runterladen.)
Primzahltests
Um herauszufinden, ob eine Zahl eine Primzahl ist, kannst du
- alle möglichen Teiler probieren (Probedivision) – Dauert für größere Zahlen zu lang.
- einen effizienteren Algorithmus verwenden (z. B. AKS-
Primzahltest oder Primzahltest mit elliptischen Kurven)
Für den Fall, dass auch der effizienteste Algorithmus zu lange braucht, gibt es probabilistische Primzahltests (z. B. Miller-
- Laut Programmierern ist es angeblich wahrscheinlicher, dass im Speicher deines Computers ein Bit umkippt als dass sich ein probabilistischer Primzahltest irrt. (War früher auch in der Mathematica-
Hilfe zu lesen, wenn ich mich richtig erinnere. Ist dort nicht mehr auffindbar. Vielleicht handelt es sich um einen Mythos.) Es sind keine Zahlen bekannt, die einen fortgeschrittenen probabilistischen Primzahltest (wie Rabin-
Miller) bestehen und doch zusammengesetzt sind.
Mathematiker unterscheiden dennoch zwischen nachgewiesenen und möglichen Primzahlen. (Letztere werden im Deutschen PRP-
Gleichungen
Für jede berechenbare Menge gibt es Gleichungen ganzer Zahlen (diophantische Gleichungen), deren ganzzahlige Lösungen genau die Elemente dieser Menge sind (Satz von Matiyasevich). Für Primzahlen gibt es:
- ein System von 14 Gleichungen mit 26 Unbekannten
- ein Polynom mit 10 Unbekannten, aber mit Grad ca. 1045
- ein System von Polynomen vierten Grades, aber mit 58 Unbekannten
Außerdem:[1]
- Formeln, die lauter (aber nicht alle) Primzahlen erzeugen
- Formeln, die die n-
te Primzahl berechnen
Für praktische Zwecke sind alle diese Gleichungen und Formeln zu kompliziert und ineffizient.
Wenn eine näherungsweise Berechnung ausreicht, gibt es jedoch einfache Formeln, z. B. dass die n-
Auswahl
In der Praxis ist es einfach, sich für eine Art des Primzahlnachweises zu entscheiden
Weiter
Quellen
| [1] | Wolfram MathWorld, Artikel Prime Number – „Although there exist explicit prime formulas (i.e., formulas which either generate primes for all values or else the nth prime as a function of n), they are contrived to such an extent that they are of little practical value.“ |