Cita:
Iniciado por ElPatoGarrido 
¿Para ver si un numero es primo basta con avanzar de 2 en 2 a partir del 3?
Suponiendo que n >= 3, entonces puedes aplicar esta micro-optimizacion. Ya que sabes que todos los demás números pares serán múltiplos de 2.
Cita:
Iniciado por ElPatoGarrido entiendo el i <= n / i, pero no sabia que no era necesario ir recorriendo cada numero desde el i hasta el sqrt(n).
Según la definición de números primos que les enseñan en la escuela es: "Cualquier numero que es divisible SOLO entre 1 y el mismo"
Pero si te pones a pensar es un poco confusa esta definición, por que cualquier entero es divisible por 1 y también obviamente por si mismo.
Entonces 2 cumple, 3 cumple pero cuando llegas a 4 te das cuenta que divisible entre el mismo y 1 (de hechos todos tienen esa propiedad) hasta que te das cuenta la parte donde dice SOLO, entonces 4 es divisible por 2 y ya no cumple con la propiedad para ser un primo. Para checar que un numero es primo tienes que checar que no tenga ningún divisor entre 2 y la raíz cuadrada de n.