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.