Hola que tal.
El metodo mas eficiente para hacer una prueba de primacia o primalidad es usando el algoritmo de Miller-Rabin, supongo que este es al que se refiere Alpha_ ya que este es obtenido a partir de algunas demostraciones matemáticas.
Sólo búsca en google: Miller Rabin primality test y encontraras el algoritmo en muchas páginas, la ventaja de este algoritmo es que es muy rápido y puedes hacer pruebas con numeros gandes, yo lo probe con numeros de hasta 1024 bits y me respondia en menos de 2 segundos, ya no lo probe con números más grandes pero también debe dar respuestas rápidas, ya que este algoritmo es usado por grandes aplicaciones matemáticas como maple.
Bueno, espero encuentres fácil de implementar el código y si tienes algunas dudas puedes preguntar.
Hasta luego.
