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.

Ein trivialer Primzahlgenerator kann folgendermaßen induktiv definiert werden:

1. $f(1)=2$
2. $f(2)=3$
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. Siehe auch Primzahltest.

Dieses Verfahren ist äußerst ineffektiv, da nacheinander alle ungeraden natürlichen Zahlen getestet werden müssen

Bisher wurde noch kein effektiver Primzahlgenerator gefunden.

siehe auch

• Primzahl#Formeln zur Generierung von Primzahlen

Informatik