En el problema en lenguaje C de encontrar números primos entre 3 y 100, un paso es sacar la raíz cuadrada. ¿Por qué?

Esto es para mejorar la eficiencia y reducir el número de juicios.

Por definición, para determinar que el número n es un número primo, es necesario determinar que n no es divisible por 2~n-1. De hecho, si n es divisible por un número entero k de 2 a n-1, entonces debe ser divisible por un número entero (n/k). Si k no es igual a (n/k), entonces uno de ellos debe ser menor que √n;

Si k es igual a (n/k), entonces k=√n debe estar presente.

Así que simplemente verifica 2~√n para determinar si n es primo. Esto puede mejorar en gran medida la eficiencia. Por ejemplo, si desea determinar que 1000003 es un número primo, de acuerdo con el algoritmo anterior, debe hacer 1000001 divisiones para tomar una decisión, mientras que usando el último algoritmo, solo necesita hacer 999; remociones de polvo para tomar una decisión. La eficiencia aumenta 1001 veces.