Si no sabe la demostracion se le adjunta, cuanto mas perfecta sea la funcion mejor calificacion tendra. Lo de que hay que llegar hast la raiz de cuadrada es posible que fuese asi, pero hasta la mitad es un razonamiento muy intuitivo y no hay que recurrir a demostraciones que puedan ser un poco mas complicadas.

¿Lo de saltarse los numeros pares no seria antes de la llamada a la funcion esprimo()?

Podrian saltarse todos los que acaban en 0 2 4 5 6 8, teniendo que comprobar solo los que acaban en 1 3 7 9 es decir un 40% de los numeros (no recuerdo si por la terminacion podia saltarse alguno mas). Todo eso es ya coger un libro de matematicas y mejorar el codigo lo maximo posible.