Primzahlgenerator

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Als Primzahlgenerator bezeichnet man in der Informatik einen Algorithmus , sodass für natürliche Zahlen der Wert die -te Primzahl ist. Bisher wurde noch kein effizienter Primzahlgenerator gefunden, insbesondere existiert keine geschlossene Formel zur Generierung von Primzahlen.

Es gibt allerdings Formeln, bei denen eine gewisse Wahrscheinlichkeit besteht, dass die erzeugten Zahlen eine Primzahl sein könnten. Trotzdem müssen die erzeugten Zahlen auf ihre Eigenschaft als Primzahl getestet werden.

Geschichte[Bearbeiten | Quelltext bearbeiten]

Einer der ältesten Algorithmen zur Bestimmung von Primzahlen ist das Sieb des Eratosthenes, bei dem nacheinander aus einer Liste der natürlichen Zahlen diejenigen Zahlen gestrichen werden, die Vielfache der jeweils kleinsten noch nicht gestrichenen Zahl sind. Dadurch bleiben die Primzahlen innerhalb der Ausgangsliste übrig.

Schon Euler gab die Formeln und an, die für bzw. Primzahlen liefern. Auch für größere Werte von liefern die beiden Formeln viele Primzahlen, weil das Ergebnis nie durch Primzahlen bzw. ganzzahlig teilbar ist. Allgemein gibt es viele solche Formeln , wodurch sich die auffällige Ulam-Spirale erklärt.

Die beliebteste ist die der Mersenne-Zahl , bei der eine Primzahl ist. Durch die besonderen Eigenschaften der Teiler von Mersenne-Zahlen eignen sie sich für die Suche nach möglichst großen Primzahlen.

Fermat vermutete, dass alle Zahlen der Form prim sind; man nennt sie Fermat-Zahlen. Tatsächlich ist aber für keine derartige Primzahl bekannt.

Auch bekannt ist eine Anwendung des Satzes von Euklid, bei der zu dem Primorial eine 1 addiert wird:

Hierbei werden alle aufeinanderfolgenden Primzahlen von 2 bis miteinander multipliziert.

ist prim für (Folge A005234 in OEIS)

Weitere Formeln[Bearbeiten | Quelltext bearbeiten]

  • ist prim für (Folge A002982 in OEIS)
  • ist prim für (Folge A002981 in OEIS)
  • Primzahlen der Form sind: (Folge A049536 in OEIS)

Trivialer Generator[Bearbeiten | Quelltext bearbeiten]

Ein trivialer Primzahlgenerator kann folgendermaßen induktiv definiert werden:

  1. für ist die auf folgende Primzahl, wobei einfach alle Zahlen ab aufsteigend darauf getestet werden, ob sie eine Primzahl sind.

Dieses Verfahren ist aber recht ineffektiv, da nacheinander alle ungeraden natürlichen Zahlen getestet werden müssen. Als Alternative bietet es sich an, mittels einer Siebmethode, z. B. Sieb des Eratosthenes oder Sieb von Atkin, eine genügend lange Liste von Primzahlen zu erstellen und diese dann bis zur gewünschten Primzahl zu durchlaufen.

Weblinks[Bearbeiten | Quelltext bearbeiten]