La criba de Eratóstenes

La criba de Eratóstenes

lunes, 23 de octubre de 2006

Página 1 de 2

La criba de Eratóstenes nos devuelve los números primos menores o iguales que uno dado.

Este es uno de los ejercicios típicos de programación. Este algoritmo se atribuye a Eratóstenes [pic 1], conocido por sus trabajos de aritmética y geometría, por tener un cargo directivo en la biblioteca de Alejandría, y por ser el primero del que se tiene constancia en demostrar que la tierra era esférica y obtener sus medidas.

No obstante, el algoritmo que nos ocupa en esta ocasión tiene que ver con aritmética. Concretamente, con números primos.

Eratóstenes descubrió éste sencillo método para obtener todos los primos menores o iguales que un número n dado.

El algoritmo es muy sencillo. Supongamos que el número que escogemos para obtener todos los números primos menores o iguales es 16. (n=16)

El algoritmo consiste en "escribir" los números comprendidos entre 2 y 16:

Primer paso:

2, 3 , 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Ahora iremos recorriendo la lista poco a poco. Utilizaremos un índice i. Empezamos por el 2. (i=2)

Recorremos la lista desde i+1 hasta n, eliminando todos los múltiplos de i. En este caso, eliminamos todos los pares (los múltiplos de 2).

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Ahora asignamos a i el siguiente número no tachado, y repetimos la operación. En este caso, i=3, y tachamos todos los múltiplos de 3 (el 6, 9, 12 y 15). Si alguno de ellos ya está tachado, pues no pasa nada.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Este paso se repite hasta que i sea mayor que la raíz cuadrada de n. (en este caso, n=16, la raiz cuadrada de n es 4). El siguiente número a escoger sería i=5, pero como 5 es mayor que 4, ya hemos acabado. Todos los números que quedan sin tachar son primos.

Por cierto, Eratóstenes no se dió cuenta de que se podía parar una vez superada la raíz cuadrada de n. Ese descubrimiento es posterior, del siglo XIII.