- Primzahlgenerator
-
Als Primzahlgenerator bezeichnet man in der Informatik einen Algorithmus f(n), so dass für natürliche Zahlen n der Wert f(n) die n-te Primzahl ist. Bisher wurde noch kein effektiver Primzahlgenerator gefunden, insbesondere existiert keine Formel zur Generierung von Primzahlen. Ein trivialer Primzahlgenerator kann folgendermaßen induktiv definiert werden:
- f(1) = 2
- f(2) = 3
- für n > = 3 ist f(n + 1) die auf f(n) folgende Primzahl, wobei einfach alle Zahlen ab f(n) + 2 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 eine genügend lange Liste von Primzahlen zu erstellen und diese dann bis zur gewünschten Primzahl zu durchlaufen.
Wikimedia Foundation.