martes, 5 de junio de 2012

Criba de Eratostenes


Hola, antes habia puesto un par de algoritmos para saber si un numero era primo, pero y si queremos saber la cantidad de primos en un intervalo dado? Tardariamos mucho si el intervalo es muy grande. Asi que lo mejor para este caso es usar el algoritmo de la criba de eratostenes.

Lo que se hace, es tomar un primo y tachar todos los multiplos de ese primo, luego tomamos el siguiente numero no tachado(que seria un primo) y eliminamos todos sus multiplos, y asi sucesivamente, hasta que todos los no primos se hayan tachado en el intervalo. Pero como sabemos eso? Pues bien, esto lo sabemos porque como se dijo antes solo necesitamos iterar hasta la raiz de un numero para saber si es primo. Es decir que cuando lleguemos a la raiz del maximo numero del intervalo habremos eliminado todos los no primos.

Asi pues, el algoritmo en java para hacer esto seria:

public static boolean criba(int n){
 boolean primos[] = new boolean[n+1];
 Arrays.fill(primos,true);
 primos[0] = primos[1] = false;
 for(int i=2;i<(int)Math.sqrt(n)+1;i++)
  if(primos[i])
   for(int j=i*i;j<primos.length;j+=i)
    primos[j] = false;
 return primos;
}


Con el primer ciclo recorremos los numeros hasta la raiz cuadrada, y con el segundo tachamos sus multiplos si el numero "i" es primo. De esta forma los valores que queden en true seran los primos, es decir primos[2] sera true.

El algoritmo en C podria ser algo como lo siguiente:

char* criba(int n){
 char *p = (char*)malloc((n+1)*sizeof(char));
 memset(p,' ', n+1);
 n = n+1;
 int i=0,j=0;
 int f = sqrt((double)n)+1;
 p[0] = p[1] = 'n';
 for(i=0;i<f;i++)
  if(p[i]==' ')
   for(j=i*i;j<n;j+=i)
    p[j]='n';
 return p;
}

Y en C los valores que queden con una 'n', no seran primos y los que queden con ' ' seran los primos, eso ya es de gustos :)

Si hay alguna pregunta o algo que agregar, comenten.

PD: les dejo unos cuantos problemas en los cuales hay que aplicar la criba para resolverlos.
http://www.codechef.com/problems/PRPALIN
http://projecteuler.net/problem=7
http://projecteuler.net/problem=10
http://projecteuler.net/problem=249

No hay comentarios:

Publicar un comentario en la entrada