Medio · Criba

Contar primos

Lee N y cuenta cuántos primos hay ≤ N. El tanteo puede pasar (un número ya lo hiciste en ¿Es primo?) — pero con N = 10.000, la criba de Eratóstenes es la diferencia entre instantáneo y lento, y tu primer algoritmo clásico como estructura de datos.

En una fraseCriba de Eratóstenes: tacha los múltiplos de cada primo hasta N y cuenta lo que queda sin tachar; para N = 10 la respuesta es 4 (2, 3, 5, 7).

El problema

Entrada: un entero N (1 ≤ N ≤ 10.000).

Salida: cuántos primos p cumplen 2 ≤ p ≤ N.

Ejemplos:

Entrada	Salida	Por qué
`10`	`4`	2, 3, 5, 7
`1`	`0`	el 1 no es primo

Tu solución

main.cpp — tu solución

Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — la idea de la criba

Crea bool es[10001], todo a true, y es[1] = false;. Recorre i desde 2: si es[i] sigue true, i es primo — cóntalo y tacha todos sus múltiplos (j = i*i, i*i+i, …). Lo que sobrevive al final es primo.

Pista 2 — dos refinamientos clásicos

Empieza a tachar en i * i, no en 2 * i: los múltiplos menores ya los tachó un primo menor (el 6 ya estaba tachado por el 2 antes de que llegue el 3). Y el bucle exterior puede parar en i * i <= n — todo compuesto ≤ n tiene un factor ≤ √n (el mismo hecho de ¿Es primo?).

Solución (¡inténtalo primero!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool is[10001];
    for (int i = 0; i <= n; i++) is[i] = true;
    is[1] = false;
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (is[i]) {
            count++;
            for (int j = i * i; j <= n; j += i) is[j] = false;
        }
    }
    cout << count << endl;
    return 0;
}

Comprobación divertida: π(10.000) = 1.229 — justo la prueba más grande del juez. La criba hace ~N·log·log N operaciones contra ~N·√N del tanteo: con N = 10.000, ~30.000 pasos contra ~1.000.000. Esa brecha — y el array de booleanos que la compra — es toda la idea de cambiar memoria por velocidad, la mitad del diseño de algoritmos. La otra mitad está en el algoritmo de Euclides.

Análisis profundo

Por qué funciona

La criba cambia memoria por tiempo: marca múltiplos en vez de probar cada número, y O(n√n) se derrumba a O(n log log n).

El coste

O(n log log n) de tiempo y O(n) de espacio. 10.000 números cuestan unos miles de operaciones en vez de un millón.

Dónde falla

Empezar el bucle interno en 2*i en vez de i*i es correcto pero redundante: cada compuesto se marca varias veces.
Un array de 10^6 int en la pila son 4 MB, cerca del límite habitual. Mantén tamaños modestos en este motor de navegador.

Siguiente paso

Otro algoritmo más antiguo que tu lenguaje: MCD.

Dos cosas para recordar

Criba: marca múltiplos, no pruebes cada número.
Cambiar memoria por tiempo es la primera decisión de ingeniería real.

🐞 Esta versión falla: ábrela y pruébala

Olvida is[1] = false: el 1 cuenta como primo

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool is[10001];
    for (int i = 0; i <= n; i++) is[i] = true;
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (is[i]) {
            count++;
            for (int j = i * i; j <= n; j += i) is[j] = false;
        }
    }
    cout << count << endl;
    return 0;
}