Criba de Eratóstenes

Eratóstenes (276 a.C – 197 a.C.) fue un matemático griego famoso por que ofreció a su rey una tabla de números primos grabada en metal. La tabla tenía agujeros en los lugares correspondientes al 1 y a los números compuestos, y se la llamó criba de Eratóstenes.

Este es un método de filtro (procedimiento sistemático para encontrar números primos) por el cual se van eliminando los números compuestos, al mismo tiempo que se van determinando por descarte, los números primos, hasta una cantidad determinada.

1. De qué trata el criba o tamiz de Eratóstenes

La manera más eficiente de encontrar todos los números primos pequeños (digamos todos aquellos menor de 10,000,000) es usando un tamiz como el Tamiz de Eratóstenes:

Haga una lista de todos los enteros menores o iguales a n (y mayores que uno). Elimina los múltiplos de todos los números primos menores o iguales que la raíz cuadrada de n, luego los números que quedan son los números primos.

Por ejemplo, para encontrar todos los números primos menores o iguales a 30, primero enumere los números del 2 al 30.

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

• El primer número 2 es primo, así que guárdelo (lo vamos a poner de color azul) y tache sus múltiplos (los colorearemos de rojo), por lo que los números rojos no son primos.

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

• El primer número que queda (aún negro) es 3, por lo que es el primer primo impar. Guárdalo y tacha todos sus múltiplos. Como 6 ya ha sido tachado (menores de 3^2), podemos comenzar a tachar desde 9.

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

• Ahora el primer número que queda (aún negro) es 5, el segundo primo impar. Así que guárdalo también y tacha todos sus múltiplos (todos los múltiplos menores a 5^2 = 25 ya han sido tachados, y de hecho 25 es el único múltiplo que aún no ha sido tachado).

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

• El siguiente número a la izquierda, 7, es más grande que la raíz cuadrada de 30, por lo que no hay múltiplos de 7 para tachar que no hayan sido tachados (14 y 28 por 2 y 21 por 3), y por lo tanto el tamiz de Eratóstenes está completo.

Por lo tanto, todos los números restantes son primos:

\[ {2, 3, 5, 7, 11, 13, 17, 19, 23, 29} \]

Observe que acabamos de encontrar estos números primos sin dividir.

2. ¿Cómo se construye la criba de Eratostenes?

Vamos a hacerlo más detallado para aplicarlo luego a un algoritmo, y posteriormente (si eres programador) a un lenguaje de programación.

Explicación con Ejemplo:

Tomemos un ejemplo cuando n = 50. Por lo tanto, necesitamos imprimir todos los números menores o iguales a 50.

• Creamos una lista de todos los números del 2 al 50.

Construir Criba de Eratostenes (1)

• De acuerdo con el algoritmo, marcaremos todos los números que son divisibles por 2.

Construir Criba de Eratostenes para múltiplos 2

• Ahora pasamos a nuestro siguiente número sin marcar (3) y marcamos todos los números que son múltiplos de 3.

Criba de Eratostenes múltiplos de 3

• Pasamos a nuestro próximo número 5 sin marcar y marcamos todos los múltiplos de 5.

Criba de Eratostenes para múltiplos de 5

• Continuamos este proceso (hasta 7, porque raíz de 50 es aproximadamente 7) y nuestra mesa final se verá a continuación:

Criba de Eratostenes múltiplos de 7

Entonces los números primos son los no marcados:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

3. Algoritmo para Criba de Eratóstenes

Eratostenes(n) {
  a[1] := 0 
  for i := 2 to n do a[i] := 1
  p := 2
  while p2 < n do {
     j := p2
     while (j < n) do { 
         a[j] := 0
          j := j+p
      }
  repeat p := p+1 until a[p] = 1 
   }
 return(a)
}

• Implementación en Java: Criba de Eratóstenes en Java

Este método es tan rápido que no hay ninguna razón para almacenar una gran lista de números primos en una computadora: una implementación eficiente puede encontrarlos más rápido de lo que una computadora puede leer desde un disco. De hecho, el problema con el algoritmo presentado anteriormente no es realmente la velocidad (utiliza O(n(log n)log log n) operaciones de bits), sino espacio (O(n)).

Entonces, para n grande usualmente usamos un tamiz segmentado. Sin embargo, tanto el tiempo como el espacio teóricamente pueden mejorarse; por ejemplo, el «algorithms based on wheels» de Paul Pritchard usa O(n log n) operaciones de bit y O(sqrt(n)/log log n) de espacio.