Criba de Erastóstenes

Para comenzar este proyecto, trataremos un algoritmo creado hace muchos años por – Sí, adivinaron – un matemático griego. Este señor inventó (¿o descubrió?) un método para encontrar todos los númerosprimos menores a un número dado. El algoritmo consiste en realizar los siguientes pasos:

Hacer una tabla con todos los números comprendidos entre 2 y n.
Tachar todos los múltiplos de 2, hastallegar al final de la tabla
Volver al principio, y buscar el primer número no tachado. Éste es un número primo.
Tachar todos los múltiplos de éste número.
Realizar los pasos 3 y 4 hasta que elcuadrado del mayor número declarado como primo es mayor que n.
Veamos un ejemplo para aclarar un poco las cosas: busquemos los número primos entre 2 y 15.

Armamos la tabla
2 3 4 5
6 7 8 9 10
11 12 1314 15
Tachamos todos los múltiplos de 2
2 3 4 5
6 7 8 9 10
11 12 13 14 15
Volvemos al principio, y notamos que el 3 es un número primo al ser el primer número no tachado después del 2.
2 3 4 56 7 8 9 10
11 12 13 14 15
Tachamos los múltiplos de 3, que no estén tachados.
2 3 4 5
6 7 8 9 10
11 12 13 14 15
Nos preguntamos: ¿Es el cuadrado de 3 mayor que 15? Como la respuesta es no (9 esmenor que 15), continuamos con el algoritmo.
Al finalizar el algoritmo, la tabla queda de esta forma:

2 3 4 5
6 7 8 9 10
11 12 13 14 15
Es claro que todos los números no tachados son primos:2, 3, 5, 7, 11, 13. ¡Buen trabajo!

Normalmente, para implementarlo en un programa se utiliza un arreglo de tipo booleano con tamaño n. Para realizar la acción de “tachar” un número dado, se colocaun valor falso en la posición correspondiente al número dentro del arreglo. Veamos el pseudocódigo:

Entrada: Número entero positivo n

Siendo Criba el arreglo booleano con los valores desde 2hasta n, inicializados en falso.

para i = 2, 3, 4, ..., hasta √n:
si A[i] es verdadero:
para j = i², i²+i, i²+2i, ..., hasta n:
A[j] := falso

Todos los valores A[i] verdaderos son...