Es sind (sehr wahrscheinlich) alle Primzahl bis weit in den Milliardenbereich hinein bekannt.
Eine neue noch unbekannte Primzahl zu finden dürfte mit einem einzelnen Computer unmöglich sein. Und die bekannten sind in irgendwelchen Listen verfügbar. Die vermutlich einfachste Lösung wäre also eine Liste von Primzahlen zu nehmen und daraus "zufällig" eine auszuwählen.
Hier ist eine Liste von "kleinen" Primtzahlen:
http://www.abide.de/docs/primzahlen.html
Um eine Zahl darauf zu Prüfen ob sie eine Primzahl ist gilt das Rabin Miller Verfahren als schnell und zuverlässig, auch wenn eine damit gefundene Zahl nicht mit 100%iger Sicherheit eine Primzahl ist. Dieses Verfahren kann man dann in einer Schleife auf Zahlen Anwenden, aber bei Zahlen über 2Mrd braucht man dann einen 128Bit Integer wenn ich mich recht erinnere.
J. Renner