Como un apasionado de la historia de las matemáticas, la Criba de Eratóstenes es uno de mis algoritmos favoritos. Es un método elegante y sorprendentemente simple para encontrar todos los números primos hasta un límite determinado. En esta guía, te explicaré qué es la Criba de Eratóstenes, quién la inventó y, lo más importante, cómo se hace con un ejemplo práctico.
La Criba de Eratóstenes es un algoritmo antiguo diseñado para encontrar todos los números primos en un rango específico. Funciona escribiendo una lista de números y tachando sistemáticamente los múltiplos de cada primo, empezando por el 2. Los números que quedan sin tachar son los primos.
El resultado final de la Criba: los números primos quedan ‘tamizados’ de los compuestos.
¿Quién Inventó la Criba de Eratóstenes?
Este ingenioso método fue creado por Eratóstenes de Cirene, un matemático, geógrafo y astrónomo griego que vivió alrededor del 276 a.C. Fue uno de los grandes eruditos de su tiempo y dirigió la famosa Biblioteca de Alejandría. Su ‘criba’ o ‘tamiz’ ha perdurado por más de dos milenios como una de las formas más intuitivas de entender los números primos.
Cómo se Hace la Criba de Eratóstenes: Ejemplo Paso a Paso (1-100)
La manera más eficiente de encontrar todos los números primos pequeños (digamos todos aquellos menor de 10,000,000) es usando un tamiz como el Tamiz de Eratóstenes.
La mejor forma de entender este algoritmo es viéndolo en acción. A continuación, te mostraré cómo se construye la criba de Eratóstenes para encontrar todos los números primos del 1 al 100.
Paso 1: La Lista Inicial
Primero, escribimos todos los números del 2 al 100.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
Paso 2: Múltiplos de 2
El primer número, 2, es primo. Lo marcamos (en azul) y tachamos o coloreamos todos sus múltiplos (en rojo).
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
Paso 3: Múltiplos de 3
El siguiente número sin marcar es el 3, nuestro segundo primo. Lo marcamos en azul y tachamos sus múltiplos restantes.
2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 24 25 262728 29 30 31 323334 35 36 37 383940 41 42 43 444546 47 48 49 505152 53 54 55 565758 59 60 61 626364 65 66 67 686970 71 72 73 747576 77 78 79 808182 83 84 85 868788 89 90 91 929394 95 96 97 9899100
Paso 4: Múltiplos de 5
Continuamos con el 5. Lo marcamos como primo y tachamos sus múltiplos.
2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 2425262728 29 30 31 3233343536 37 383940 41 42 43 444546 47 48 49 505152 53 5455565758 59 60 61 6263646566 67 686970 71 72 73 747576 77 78 79 808182 83 8485868788 89 90 91 9293949596 97 9899100
Paso 5: Múltiplos de 7 y Finalización
El último primo que necesitamos comprobar es el 7. Lo marcamos y tachamos sus múltiplos. Como el siguiente primo (11) al cuadrado es 121 (que es mayor que 100), el proceso ha terminado.
2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 2425262728 29 30 31 3233343536 37 383940 41 42 43 444546 47 4849505152 53 5455565758 59 60 61 6263646566 67 686970 71 72 73 7475767778 79 808182 83 8485868788 89 90919293949596 97 9899100
Resultado Final: La Criba de Eratóstenes Resuelta
¡Y listo! Los números que quedaron sin tachar son los 25 números primos hasta 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Descarga la Tabla de la Criba en PDF
Para facilitar tus estudios o clases, he preparado una versión imprimible de la criba de Eratóstenes del 1 al 100 en formato PDF. ¡Descárgala gratis!
Descargar Criba de Eratóstenes (1-100) en PDF
Ejemplo Gráfico: Construyendo la Criba del 1 al 50
Vamos a hacerlo más detallado para aplicarlo luego a un algoritmo, y posteriormente (si eres programador) a un lenguaje de programación.
Explicación con Ejemplo:
Tomemos un ejemplo cuando n = 50. Por lo tanto, necesitamos imprimir todos los números menores o iguales a 50.
- Creamos una lista de todos los números del 2 al 50.
Construir Criba de Eratostenes (1)
- De acuerdo con el algoritmo, marcaremos todos los números que son divisibles por 2.
Construir Criba de Eratostenes para múltiplos 2
- Ahora pasamos a nuestro siguiente número sin marcar (3) y marcamos todos los números que son múltiplos de 3.
Criba de Eratostenes múltiplos de 3
- Pasamos a nuestro próximo número 5 sin marcar y marcamos todos los múltiplos de 5.
Criba de Eratostenes para múltiplos de 5
- Continuamos este proceso (hasta 7, porque raíz de 50 es aproximadamente 7) y nuestra mesa final se verá a continuación:
Criba de Eratostenes múltiplos de 7
Entonces los números primos son los no marcados:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
El Algoritmo de la Criba de Eratóstenes (Para Programadores)
Para los más técnicos, este método se traduce en un algoritmo muy eficiente para la computación. A continuación se presenta un pseudocódigo básico que ilustra su lógica:
function Eratostenes(n):
// Crear una lista booleana "es_primo" de tamaño n+1
// e inicializar todas las entradas como verdaderas.
es_primo = [true for i in range(n + 1)]
p = 2
while (p * p <= n):
// Si es_primo[p] no ha cambiado, entonces es primo
if (es_primo[p] == true):
// Actualizar todos los múltiplos de p
for i in range(p * p, n + 1, p):
es_primo[i] = false
p += 1
// Imprimir todos los números primos
for p in range(2, n + 1):
if es_primo[p]:
print(p)
Ahora que entiendes cómo funciona la criba, puedes usar mi generador de listas de primos para crear listas de cualquier tamaño, o el verificador para comprobar números individuales.