Algoritmo clásico de cribado que enumera todos los números primos hasta una cota N marcando iterativamente como compuestos los múltiplos de cada primo empezando en 2; los números no marcados son primos.

Principio

Eliminar sistemáticamente múltiplos: para cada primo candidato p empezando en 2, marcar múltiplos kp (k ≥ 2) hasta N; los números no marcados no tienen factor primo menor y por tanto son primos.

Demostración

Primos ≤ 30. Inicializar 2..30, marcar múltiplos de 2 (4,6,...,30), siguiente no marcado 3 marcar 6,9,..., luego 5 marcar 10,15,... Resultado no marcado: 2,3,5,7,11,13,17,19,23,29.

Aplicación incorrecta

Usar el criba ingenuo en memoria completa para N extremadamente grande sin segmentación, o aplicar el criba a rangos no enteros o negativos; olvidar que 1 no es primo.

Consecuencia

Produce la lista completa de primos hasta N con tiempo aproximado O(N log log N) y una disposición de memoria simple; base para generación de primos y optimizaciones segmentadas o por ruedas.

Inversión

La inversión sería intentar determinar la primalidad de un solo número muy grande cribando desde 2 hasta él — ineficiente frente a pruebas de primalidad dirigidas; el criba es mejor para intervalos que para un único valor enorme.

Límite

Destinado a enumerar primos hasta una cota N moderada; para cotas muy grandes usar variantes segmentadas u optimizadas por ruedas. El criba estándar se aplica a índices naturales y no da pruebas de primalidad fuera del intervalo.

Tensión semántica

Se contrapone a la división por ensayo (comprobar cada candidato dividiéndolo por primos) y a pruebas probabilísticas de primalidad; los cribas enumeran primos en bloque, mientras que las pruebas atienden la primalidad individual con perfiles de coste distintos.

Síntesis

La criba de Eratóstenes es el procedimiento eliminatorio directo que marca múltiplos de primos hallados para revelar todos los primos hasta una cota, constituyendo la base para una enumeración masiva eficiente.