Intermedio · bucles anidados
Contar los primos
¿Cuántos primos hay hasta n? El primer problema donde el bucle interno es el protagonista — y donde break es rendimiento, no estilo.
Problema
Entrada: un entero n (0 ≤ n ≤ 10⁶).
Salida: el número de primos p con p ≤ n.
Ejemplo:
| Entrada | Salida |
|---|---|
10 | 4 |
100 | 25 |
Tu solución
Entrada personalizada para "Probar mi entrada"
La corrección se ejecuta por completo en tu navegador contra pruebas ocultas. Tu código se guarda localmente mientras escribes. Ctrl+Enter corrige.
¿Atascado? Pistas
Pista 1 — reutiliza Comprobar primo
La prueba interna es exactamente el problema Comprobar primo: división por tentativa hasta √i, con break en el primer divisor. Envuélvelo en un bucle de 2..n y cuenta.
Pista 2 — por qué importa el break
Sin break pruebas todos los divisores de todos los números. Con él, la mayoría sale tras una o dos divisiones. Con n = 10⁶ esa es la diferencia entre segundos y un timeout.
Solución (¡inténtalo primero!)
int n = int.Parse(Console.ReadLine());
int count = 0;
for (int i = 2; i <= n; i++)
{
bool prime = true;
for (int d = 2; d * d <= i; d++)
{
if (i % d == 0) { prime = false; break; }
}
if (prime) count++;
}
Console.WriteLine(count);El siguiente paso es la criba de Eratóstenes — un array de booleanos en vez de división por tentativa, que convierte O(n√n) en O(n log log n). Siguiente: Número de Armstrong.