Bachiller

La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado N. Se forma una tabla con todos los números naturalescomprendidos entre 2 y N y se van tachando los números que no son primos de la siguiente manera: cuando se encuentra un número entero que no ha sido tachado, ese número esdeclarado primo, y se procede a tachar todos sus múltiplos. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que N.
Refinamiento: Unaimplementación más eficiente requiere crear un arreglo con solo los impares (pues los pares distintos de 2 ya se sabe que no son primos). En este caso se deben tachar losmúltiplos impares de 3,4,5,7.
Los múltiplos impares del primo  son . Debemos tachar desde  en adelante pues siempre se empieza a tachar desde . Note que si  entonces el primermúltiplo de  es .
Si corresponde tachar los múltiplos del primo ésimo , se inicia en  pues antes de , ya se han tachado  (los pares),  (los múltiplos de 3), ,...,. Así, si  ya nohabría algo que tachar, por eso terminamos ahí el programa.
En la implementación se usa un arreglo "esPrimo()" tipo boolean. Aquí, "esPrimo(i)" representa al númeroimpar .Note que si  entonces  está representado por "esPrimo((p-3)/2)".
Así, si se sabe que  es primo, sus múltiplos (impares) no son primos, es decir, debemos poner"esPrimo(((2k+1)p-3)/2)=false, k=i+1,i+2,..."
En la implementación iniciamos con el arreglo "esPrimo()" con todas sus entradas true.Iniciando en , ponemos "esPrimo(((2k+1)3-3)/2)=false,k=0+1,0+2,..." y así sucesivamente: para cada nuevo  primero preguntamos si "esPrimo(i)=true", si es así, "tachamos" sus múltiplos poniendo la respectiva entrada "false".