Si el rango que permite tu aplicación no es exageradamente extenso podrías tener una lista de numeros primos en tu código. Eso te solucionaría el problema fácilmente. Te dejo un
enlace dónde puedes bajarte una lista extensa de numeros primos. Suerte.