Introducción

La Criba de Eratóstenes es uno de los algoritmos más antiguos y eficientes para generar todos los números primos menores o iguales a un número n. Fue descrita por el matemático griego Eratóstenes de Cirene alrededor del siglo III a.C. y sigue siendo la base de muchas aplicaciones modernas, desde criptografía hasta pruebas de primalidad en competiciones de programación.

Principios matemáticos

• Un número primo es aquel que solo es divisible por 1 y por sí mismo.
• Si un número p es primo, todos sus múltiplos k·p (con k ≥ 2) no pueden ser primos.
• Para encontrar todos los primos ≤ n basta marcar los múltiplos de cada primo encontrado, empezando por 2 y continuando hasta √n.

Estructura del algoritmo

El algoritmo se puede dividir en cuatro fases claras:

1. Inicialización: crear una lista booleana es_primo[0..n] inicializada a True (excepto 0 y 1).
2. Iteración principal: recorrer i desde 2 hasta √n. Si es_primo[i] es True, i es primo.
3. Marcado de múltiplos: para cada primo i, marcar como False todos los múltiplos i·i, i·i+i, … ≤ n.
4. Salida: los índices que permanecen True son los números primos.

Complejidad y análisis de rendimiento

Implementación en Python (versión básica)

def criba_eratostenes(n: int) -> list[int]:
    """Devuelve la lista de primos ≤ n usando la criba clásica."""
    if n < 2:
        return []
    # Paso 1: crear tabla booleana
    es_primo = [True] * (n + 1)
    es_primo[0] = es_primo[1] = False
    # Paso 2: iterar hasta √n
    limite = int(n ** 0.5) + 1
    for i in range(2, limite):
        if es_primo[i]:
            # Paso 3: marcar múltiplos a partir de i*i
            for j in range(i * i, n + 1, i):
                es_primo[j] = False
    # Paso 4: extraer primos
    return [i for i, primo in enumerate(es_primo) if primo]

Esta versión es suficiente para n hasta ~10⁶ sin problemas. Sin embargo, existen optimizaciones que pueden multiplicar su rendimiento.

Optimizaciones avanzadas

• Usar bytearray en lugar de lista de bool: reduce la huella de memoria y acelera el acceso.

  es_primo = bytearray(b"\x01") * (n + 1)

• Ignorar los números pares: iniciar la tabla sólo con los números impares y tratar 2 por separado.

  size = (n // 2)  # solo impares
  es_primo = bytearray(b"\x01") * (size)
  for i in range(3, int(n**0.5)+1, 2):
      if es_primo[i//2]:
          es_primo[i*i//2 :: i] = b"\x00" * ((size - i*i//2 - 1)//i + 1)
  primos = [2] + [2*i+1 for i, v in enumerate(es_primo) if v]
  

• Segmented Sieve: dividir el rango en bloques que caben en caché L2/L3, útil cuando n > 10⁹.

  def segmented_sieve(limit):
      import math
      segment_size = int(math.sqrt(limit)) + 1
      # Criba base
      base = criba_eratostenes(segment_size)
      # Procesar bloques
      low = segment_size
      high = 2 * segment_size
      while low < limit:
          if high > limit:
              high = limit
          block = bytearray(b"\x01") * (high - low)
          for p in base:
              start = ((low + p - 1) // p) * p
              for j in range(start, high, p):
                  block[j - low] = 0
          yield [i+low for i, v in enumerate(block) if v]
          low += segment_size
          high += segment_size
  

Casos de uso reales

• Criptografía: generación de primos para RSA (aunque normalmente se usan pruebas probabilísticas, la criba ayuda a obtener candidatos pequeños).
• Programación competitiva: pre‑cálculo de primos ≤ 10⁶ para resolver problemas de factorización rápida.
• Análisis de datos: filtrado de números en bases de datos donde se requiere identificar valores primos.

Resolución de problemas comunes (troubleshooting)

1. Memoria insuficiente para n grande: cambie a segmented sieve o use una estructura de bits (biblioteca bitarray).
2. Tiempo de ejecución inesperadamente alto: asegúrese de que el bucle de marcaje empiece en i*i y no en 2*i. Verifique que está usando range(i*i, n+1, i).
3. Resultados incorrectos para n < 2: añada una condición explícita que retorne una lista vacía.

Buenas prácticas y estilo de código

• Documente la función con una docstring completa (parámetros, retorno, complejidad).
• Utilice tipado estático (-> list[int]) para facilitar la lectura y el análisis estático.
• Prefiera variables descriptivas (es_primo, limite) sobre abreviaturas crípticas.
• Incluya pruebas unitarias con pytest que cubran casos límite (0, 1, 2, números grandes).

Conclusión

La Criba de Eratóstenes sigue siendo una herramienta fundamental en el arsenal de cualquier ingeniero de software o científico de datos que necesite trabajar con números primos. Su simplicidad, eficiencia y facilidad de paralelización la hacen ideal tanto para proyectos académicos como para aplicaciones de producción. Aprovechando las optimizaciones modernas —bytearrays, criba de impares y segmentación— es posible escalar el algoritmo a rangos de varios miles de millones sin sacrificar rendimiento.