La criba de Eratóstenes
Detalles- Detalles
- Categoría: Programación
- Publicado el Lunes, 23 Octubre 2006 11:48
Este es uno de los ejercicios típicos de programación. Este algoritmo se atribuye a Eratóstenes, 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 fundamento
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.
Construyendo el algoritmo
Lo malo de este algoritmo es la cantidad de memoria que consume, que crece linealmente conforme n se va haciendo más grande. Además, el número de "tachones" crece también conforme n se va haciendo más grande, pero exponencialmente.
No obstante, el algorimo es sencillo de construir
Aquí tienes una posible descripción en pseudocódigo y una implementación en C#
pseudo
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 26 27 | funcion Criba(n:entero):lista de enteros variables: l:lista de enteros i,r:entero vb: vector de booleanos con índices 2..n; empieza: inicializar vb a false i=2 r=raiz cuadrada de n mientras i<r si vb[i] es false poner a true los lugares de vb múltiplos de i finSi i=i+1 finMientras para todo j desde 2 hasta n si vb[j] es false añadir j a l finSi finPara devolver l fin |
C#
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 26 27 28 29 30 31 32 33 34 35 36 37 38 | List<long> Criba(long n) { //almacenaremos los resultados de la //criba en una lista para devolverla List<long> l = new List<long>(); //Creamos un array de booleanos para poder //tachar. False=no tachado. True=tachado //desperdiciamos los lugares 0 y 1, pero el //algoritmo queda más claro. bool[] vb=new bool[n+1]; for (int j = 0; j <= n; j++) vb[j] = false; //empezamos con i=2; long i = 2; long raiz=(long)Math.Sqrt(n); while (i <= raiz) { //si i no está tachado if(!vb[i]) //tachamos todos sus múltiplos for (long j = i + i; j <= n; j = j + i) vb[j] = true; //pasamos al siguiente i++; } //ahora metemos en la lista todos los que están //sin tachar for (long j = 2; j <= n; j++) if (!vb[j]) l.Add(j); //devolver la lista con los primos return l; } |
En fin, un algoritmo no demasiado difícil de implementar, pero tampoco muy eficiente. Se nos podría ocurrir alguna optimización, pero tampoco llegaríamos muy lejos. Por ejemplo, es fácil darse cuenta de que todos los pares a excepción del 2 quedan siempre tachados. Así pues podríamos ahorrarnos la mitad del vector (a costa de complicar un poco los índices).
