El último método que vamos a estudiar para encontrar primos es la Criba de Eratóstenes. Supongamos que necesitamos saber rápidamente si varios números son primos o no dentro de cierto rango. Cuando la cantidad de números a analizar crece, cualquiera de los dos métodos anteriores tomaría demasiado tiempo y resultan poco prácticos.

La ventaja de la Criba es que podemos acceder a un arreglo para ver si el número es primo, la gran desventaja es que el arreglo tiene que ser tan grande como el rango que vamos a utilizar por lo que generalmente consume una gran cantidad de memoria.

Este algoritmo es el que comúnmente se enseña en las primarias: primero hacemos una lista con todos los números que vamos a utilizar. Agarramos el primer primo (el dos) y vamos tachando todos sus múltiplos, después tomamos el siguiente número que no está marcado (el tres) y tachamos sus múltiplos, y así sucesivamente hasta que recorremos todos los números. Por ejemplo, para los primeros cien números:

Figura 4.1: Criba de Eratóstenes para los número del 0 al 99

Solución: Lo primero que debemos observar es que todos los números primos, excepto el dos, son impares. Si a y b son impares la suma va a ser par, por lo que no puede ser primo. Para que las suma sea impar uno de los sumandos debe ser par y el otro impar, y como el que es par también tiene que ser primo la única posibilidad es que sea el dos. Lo que tenemos ahora es a + 2 = c, con a y c primos, que lo podemos cambiar a c –a = 2.

A las parejas de primos cuya diferencia es dos se les conoce como primos gemelos y tienen la particularidad de que a excepción de la pareja (3, 5), las demás parejas son de la forma (6n –1, 6n + 1).

Esto lo podemos comprobar de la siguiente manera: cualquier número natural se puede expresar de la forma 6n + k, donde k está en el rango de 0 a 5 y n ≥ 0. Excluyendo cuando n = 0, si k = 0, 2, 3 ó 4 el resultado no es primo por ser divisible ya sea entre dos o entre tres. Sólo queda los casos k = 1 y 5, que los podemos expresar también como k = 1 y –1, y pueden o no ser primos, por lo que son los que vamos a revisar en el programa.




Empezamos declarando las variables que vamos a utilizar (líneas 1 a 3): i es una variable para ciclos, n es el número que no debe superar la suma, t es el total de parejas que cumplen y num es un arreglo para saber si un número es primo.

El procedimiento Criba es donde vamos a determinar cuales números son primos y cuales son compuestos (líneas 5 a 26). Se declaran primero en la línea 6 las variables i y j que serán usadas para los ciclos. Empezamos quitando el uno y poniendo al dos como primo en la línea 8. Después quitamos todos los múltiplos de dos y dejemos todos los impares (líneas 9 a 11).

El ciclo que está de la línea 13 a la 25 es donde realizamos la mayor parte del trabajo. Primero buscamos cual número todavía no esta tachado, ya que es el siguiente número primo. Ya que lo encontramos, nos vamos hasta el cuadrado del número y empezamos a tachar todos sus múltiplos impares (líneas 17 a 22), para irnos un poco más rápido. Nos saltamos hasta el cuadrado porque ya hemos tachado todos los múltiplos anteriores.

La siguiente parte es la principal del programa (líneas 28 a 40). Empezamos por leer n, que es el número que no debe superar la suma (línea 29). En la siguiente línea mandamos calcular la Criba hasta n. En las líneas 31 y 32 inicializamos el contador: si n es mayor que cuatro agregamos la pareja (3, 5), si es menor o igual entonces no existen parejas. En las líneas 33 a 35 hacemos un recorrido para contar cuantas parejas cumplen e imprimimos el resultado. En la línea 36 imprimimos la pareja que es distinta y en las líneas 37 a 39 volvemos a hacer el barrido para imprimir las parejas que se encontraron.

Entrada:	25
Desarrollo:	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 t= 1 i= 1, (5, 7),   t= 2 i= 2, (11, 13), t= 3 i= 3, (17, 19), t= 4 i= 4, (23, 25), t= 4
Salida:	4 2 3 5 7 11 13 17 19

Lenguaje	Fecha	Tiempos [s]				Memoria [Kb]
		Ejecución	Mejor	Mediana	Peor
Pascal	12-Ene-2006	0.163	0. 024	-	-	905
C	16-Feb-2006	0.204				2314