Pra quem gosta desse desafio, recomendo dar uma olhada (ou estudada) num algoritmo chamado "Sieve of Eratosthenes".
Acho que ainda é a implementação mais rápida para teste de primalidade. Ele usa essa a técnica descrita pelo Fred e expande com algumas outras.
Bastante teoria dos números e fatoração!
Dei uma leve estudada nesse algoritmo quando precisei estudar (quebra de) criptografia e "de quebra" acabei em fatoração pesada, gcd, etc. Cheguei a sonhar com uma idéia de quebrar os certificados digitais gerados pela openssl. Aí eu acordei! haha :D No mês seguinte publicaram um bug