Se devi generare più di qualche decina di numeri, ad occhio mi parrebbe più efficiente prima generare tutti i numeri primi minori di 1000 e metterli in un array, quindi pescare a caso elementi dall'aray in questione.