La criba de Eratóstenes es un algoritmo que nos permite encontrar todos los números primos menores que un numero dado n. Se llama asi por el matematico griego Eratostenes de Cyrene, al que se le atribuye su descubrimiento. El algoritmo funciona creando un arreglo de tamaño n, en el que se marcan los números primos como verdaderos y sus múltiplos como falso. El algoritmo inicialmente asume a todos los números como primos, excepto el 1. Posteriormente, vamos a tomar siempre el menor numero asumido como primo, y vamos a descartar a todos sus múltiplos (los marcamos como false en el arreglo), ya que estos no pueden ser primos. Finalmente en la tabla quedaran solo los números primos marcados con true.
Una forma sencilla de escribir el algoritmo seria la siguiente:
public boolean[] sieve(int N)
{
boolean[] table = new boolean[N + 1];
Arrays.fill(table, true);
table[0] = table[1] = false;
for(int i = 2; i <= N; i++)
if(table[i])
for(int j = i*2; j <= N; j += i) table[j] = false;
return table;
}
El código anterior es correcto, pero puede ser optimizado realizando algunas observaciones. En el ciclo interior, donde iteramos por los múltiplos del numero para descartarlos como primos, comenzamos siempre en i×2. Sin embargo podemos comenzar en i×i, ya que todos los múltiplos menores han sido descartados por los números mas pequeños que i. Por ejemplo, el 6 es descartado 2 veces. Primero por el 2 ya que 2×3 = 6, y después por el 3 ya que 3×2=6. Tomando esto en cuenta, solo tendríamos que iterar hasta la raíz de N, ya que el menor numero que elevado al cuadrado es N, es su raíz y a partir de este numero, ninguno mas sera descartado, porque todos los que quedan entre el y N han sido descartados por los múltiplos menores.
Con esta modificación, el codigo quedaria asi:
public boolean[] sieve(int N)
{
boolean[] table = new boolean[N + 1];
Arrays.fill(table, true);
table[0] = table[1] = false;
for(int i = 2; i*i <= N; i++)
if(table[i])
for(int j = i*i; j <= N; j += i) table[j] = false;
return table;
}
Otra posible optimización es notar que ningún numero par puede ser primo, ya que es divisible por 2. Por tanto podemos descartarlos al comienzo de la criba y considerar solamente los números impares como posibles primos. De esta forma reducimos los candidatos a la mitad.
public boolean[] sieve(int N)
{
boolean[] table = new boolean[N + 1];
for(int i = 3; i <= N; i+=2) table[i] = true;
table[2] = true;
for(int i = 3; i*i <= N; i+=2)
if(table[i])
for(int j = i*i; j <= N; j += i) table[j] = false;
return table;
}
De esta manera obtenemos un algoritmo de orden O(n×log n×log log n).
Calcular la cantidad de primos menores que n
Este algoritmo puede ser modificado para ayudarnos a resolver problemas relacionados con los números primos. Por ejemplo, podríamos calcular también cuantos números primos hay hasta un numero dado n. Solo tenemos que almacenar otro arreglo y acumular la cantidad de primos hasta la posición i. Esto lo logramos sumando en cada paso los primos calculados hasta i-1, y si la posición i es un numero primo, incrementamos el arreglo.
public int[] sieve(int N)
{
boolean[] table = new boolean[N + 1];
for(int i = 3; i <= N; i+= 2) table[i] = true;
table[2] = true;
for(int i = 3; i*i <= N; i+= 2)
if(table[i])
for(int j = i*i; j <= N; j += i) table[j] = false;
int[] amount = new int[N+1];
for(int i = 2; i <= N; i++)
{
amount[i]+= amount[i-1];
if(table[i]) amount[i]++;
}
return amount;
}
Descomponer en factores primos
Este algoritmo también puede ser modificado para descomponer un numero en sus factores primos. Para lograr esto, tenemos que mantener un arreglo y en cada posicion marcaremos el mayor numero primo que descarto a ese numero.
public int[] sieve(int N)
{
boolean[] table = new boolean[N + 1];
int[] factors = new int[N + 1];
for(int i = 2; i <= N; i+=2) factors[i] = 2;
for(int i = 3; i <= N; i+=2)
{
table[i] = true;
factors[i] = i;
}
table[2] = true;
for(int i = 3; i*i <= N; i+=2)
if(table[i])
for(int j = i*i; j <= N; j += i)
{
table[j] = false;
factors[j] = i;
}
return factors;
}
Una vez que tengamos este arreglo, podemos descomponer un numero en factores primos dividiéndolo entre el numero que lo marco, y siguiendo la tabla hasta llegar a 1. Veamos la secuencia de acciones para descomponer el numero 210:
- El valor del arreglo en 210 es 7. Dividimos 210/7 = 30.
- El valor en 30 es 5. Dividimos 30/5 = 6.
- El valor en 6 es 3. Dividimos 6/3 = 2.
- El valor en 2 es 2. Dividimos 2/2=1.
De esta forma encontramos que los factores primos son 7, 5, 3, y 2.
Referencias
es.wikipedia.org/wiki/Criba_de_Erat%C3%B3stenes
mathworld.wolfram.com/SieveofEratosthenes.html
rosettacode.org/wiki/Sieve_of_Eratosthenes
Programacion Deportiva 