Mario Sedlak
Mathematik
Wissenschaft
Hauptthemen
Neue und erweiterte Seiten

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

Für den Fall, dass auch der effizienteste Algorithmus zu lange braucht, gibt es probabilistische Primzahltests (z. B. Miller-Rabin-Test oder Baillie-PSW-Primzahltest). Diese sind viel schneller, aber mit einer gewissen Wahrscheinlichkeit weisen sie eine Zahl als Primzahl aus, obwohl diese gar keine Primzahl ist ("Pseudoprimzahl"). In der Praxis kann diese Irrtumswahrscheinlichkeit vernachlässigt werden:

Mathematiker unterscheiden dennoch zwischen nachgewiesenen und möglichen Primzahlen. (Letztere werden im Deutschen PRP-Zahlen genannt; im Englischen einfach probable primes).

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:

Außerdem:[1]

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-te Primzahl ungefähr n ln n ist. (Siehe Anzahl von Primzahlen)

Auswahl

In der Praxis ist es einfach, sich für eine Art des Primzahlnachweises zu entscheiden

Weiter

Erweiterungen der gängigen Zahlenbereiche

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."

Seite erstellt am 25.3.2024 – letzte Änderung am 25.3.2024