Acredito que não seria necessário testar se ele é divisível pelos primos abaixo de 5000, apenas se ele não é par. se \sqrt[]{n} for próximo de 5000 daí então o teste faz sentido, se for igual não é necessário continuar com o código e se for menor o mesmo ocorre.