Edición didáctica en español. El código y sus salidas conservan el original.
Criba de Eratóstenes en C
Encuentra todos los primos hasta un límite marcando sus múltiplos.
Crea un array que indique los candidatos desde 0 hasta N. Marca 0 y 1 como no primos. Para cada candidato primo p, elimina sus múltiplos; puedes empezar en p * p porque los múltiplos menores ya tienen un factor menor.
Solo necesitas iniciar marcas para p hasta la raíz de N. Evita desbordamientos en p * p cuando generalices a límites grandes, por ejemplo comparando p <= N / p con p positivo. Comprueba que el buffer incluya el índice N.
La criba clásica utiliza O(N) de memoria y aproximadamente O(N log log N) de tiempo. Prueba límites 0, 1, 2 y un valor mayor; el límite puede requerir adaptar el ejemplo.
Código C
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
void sieve(int n) {
bool isPrime[n + 1];
memset(isPrime, true, sizeof(isPrime));
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
printf("Primes up to %d:\n", n);
for (int p = 2; p <= n; p++) {
if (isPrime[p]) printf("%d ", p);
}
printf("\n");
}
int main() {
int n = 50;
sieve(n);
return 0;
}Salida esperada
Primes up to 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Preguntas frecuentes
¿Por qué el código y la salida siguen en inglés?
Las palabras clave, los identificadores y los textos que verifican las pruebas se conservan para no cambiar el programa. Las explicaciones y los controles están traducidos.