Medio · Lógica de bucles
¿Es primo?
Lee un entero e imprime si es primo. Fácil de enunciar — y el primer problema donde cómo buclas importa tanto como si buclas.
En una frasePrueba divisores solo hasta √N y corta en el primero que divida: 1 no es primo, 2 sí, y el límite √N deja el bucle en unos mil pasos para N = 10⁶.
El problema
Entrada: un entero N (1 ≤ N ≤ 1.000.000).
Salida: prime si N es primo; si no, not prime (exactamente estas palabras).
Ejemplos:
| Entrada | Salida |
|---|---|
17 | prime |
18 | not prime |
Un primo tiene exactamente dos divisores: 1 y sí mismo. Así que 1 no es primo, y 2 es el único primo par.
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 — asumir, refutar, concluir
Arranca con bool prime = true;. Recorre divisores candidatos; en cuanto uno divida exacto (n % i == 0), marca prime = false; y break; — un solo contraejemplo basta. Al final, imprime según la bandera.
Pista 2 — no necesitas llegar hasta N
Si N tiene un divisor mayor que √N, también tiene uno menor que √N (van en pareja: d × (N/d) = N). Basta con i * i <= n — para N = 1.000.000 son 1.000 candidatos en lugar de un millón. Bordes: N = 1 no es primo; N = 2 sí.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
bool prime = true;
if (n < 2) prime = false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
prime = false;
break;
}
}
if (prime) cout << "prime" << endl;
else cout << "not prime" << endl;
return 0;
}Las tres ideas — asumir-y-refutar, break al primer contraejemplo y el atajo de √N — reaparecen en todos los problemas de números. Buena meta: imprimir todos los primos hasta N (un bucle exterior más, o investiga la criba de Eratóstenes — que es justo el siguiente problema).
Análisis profundo
Por qué funciona
Asumir y luego refutar: empiezas con prime = true y buscas un solo contraejemplo. Esa forma es el esqueleto de todo bucle de validación que escribas.
El coste
O(√n) con la cota i * i <= n. Para 1.000.000 son 1.000 vueltas en vez de un millón: mil veces más rápido por una línea.
Dónde falla
i <= sqrt(n)recalcula una raíz en coma flotante en cada vuelta y se desvía por redondeo.i * i <= nes exacto y más rápido.- Olvidar
n < 2hace que 0 y 1 salgan primos.
Siguiente paso
Todos los primos hasta N, bien hecho: Contar primos.
Dos cosas para recordar
- Los divisores vienen en parejas: para en √n.
- 1 no es primo; 2 es el único primo par.
🐞 Esta versión falla: ábrela y pruébala
i * i < n se salta los cuadrados perfectos
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
bool prime = true;
if (n < 2) prime = false;
for (int i = 2; i * i < n; i++) {
if (n % i == 0) {
prime = false;
break;
}
}
if (prime) cout << "prime" << endl;
else cout << "not prime" << endl;
return 0;
}