Criba de Eratóstenes

Tema: Matemática y Combinatoria · temarios: Syllabus OCI · Syllabus IOI

📍 Ampliación: parte de divisibilidad y MCD del módulo 10. Esta técnica se desarrolla en la ficha, no en esa clase.

Qué problema resuelve

Un primo es un entero mayor que 1 cuyos únicos divisores positivos son 1 y él mismo. Si necesitas todos los primos hasta un límite n, comprobar cada número por separado repite mucho trabajo. La criba comparte ese trabajo: cuando encuentra un primo, marca sus múltiplos como compuestos.

Conviene para muchas consultas dentro de un rango moderado. Para consultar o factorizar unos pocos números grandes, compara con la división de prueba de Factorización. El límite del valor, y no la cantidad de consultas, determina el tamaño de la criba.

Un ejemplo hasta 20

Empezamos considerando candidatos a 2, 3, …, 20. El 0 y el 1 no son primos.

Primo encontradoMúltiplos que intentamos marcar desde su cuadrado
24, 6, 8, 10, 12, 14, 16, 18, 20
39, 12, 15, 18
5ninguno: 25 ya supera 20

Al seguir recorriendo los candidatos, sobrevivirán 2,3,5,7,11,13,17,19.

¿Por qué empezar en p*p? Los múltiplos 2p,3p,…,(p−1)p ya tienen un factor primo menor que p, así que se marcaron antes. Volver a marcarlos sería correcto, pero innecesario.

¿Por qué un número que sobrevive es primo? Si fuera compuesto, tendría un factor primo menor que él y ese factor ya habría marcado su múltiplo. Por otro lado, solo marcamos productos de al menos dos enteros mayores que 1, así que no eliminamos primos.

Implementación recomendada (C++)

// Criba de Eratóstenes: tacha los múltiplos de cada primo que va encontrando.
vector<int> criba(int n) {
    vector<bool> compuesto(n + 1, false);
    vector<int> primos;
    for (int i = 2; i <= n; i++) {
        if (compuesto[i]) continue;                 // sobrevivió sin tachar: es primo
        primos.push_back(i);
        for (long long j = (long long)i * i; j <= n; j += i)
            compuesto[j] = true;                    // desde i*i: los menores ya se tacharon
    }
    return primos;
}

El contrato es 0 <= n < INT_MAX, y deben caber en memoria tanto la tabla como la lista de resultados. Para n=0 y n=1 se devuelve una lista vacía. La tabla interna compuesto no se devuelve: en ella 0 y 1 tampoco se marcan, pero el recorrido de candidatos empieza en 2. Si adaptas la tabla para responder consultas de primalidad, trata 0 y 1 explícitamente.

El producto se convierte a long long antes de multiplicar para que i*i no desborde un int.

Costo: O(n log log n) tiempo y O(n) memoria, contando resultados. vector<bool> guarda marcas de forma compacta; además se almacena un int por primo. No asumas que un límite de miles de millones cabe solo porque las marcas son booleanas.

Qué devuelve y qué no

Esta función devuelve los primos. No guarda el menor factor primo de cada número. Para factorizar repetidamente puedes probar divisores de la lista hasta la raíz del valor restante, o construir otra criba que sí almacene el menor factor; esa variante exige más memoria que una marca por número.

Para comprobarlo

Predice la salida para 1, 2 y 10. Después decide cuál herramienta usarías para estas tareas: enumerar todos los primos hasta un millón; factorizar un único entero cercano a un billón (10^12). La cantidad de datos y el rango son distintos: no necesitas reservar un billón de posiciones para la segunda tarea.