Tu pregunta es muy buena de verdad, tanto que no tienes muchas respuestas, pues si dado un entero z yo se cuáles son sus divisores sabría si es primo o si no lo es ¿no?, pues encontrar los divisores es equivalente a una descomposición de números primos, luego si yo supiera fácilmente si el número es primo o no uff ganaría millones, pues empresas de seguridad pagan por obtener primos para criptografía y otras cosas y ¿qué crees? lo más rentable es intentar descomponer el número dividiendolo entre los menores, como sabrás los criterios de divisibilidad no son simples ahora imagínate números grandísimos, así que en conclusión, no, no hay manera de hacer eso más rápido.
