La Criba de Eratóstenes

Todos vosotros sabéis qué son los número primos, y por tanto no dudareis al afirmar que 7 es un número primo, y que 10 es número compuesto. ¿Por qué? Porque un número primo es un número natural que tiene exactamente dos divisores distintos: él mismo y el 1, como ocurre con 7 = 7 · 1. Mientras que los número compuestos son aquéllos que tienen algún divisor natural aparte de él mismo y del 1, como podemos ver en el caso de 10 = 1 · 2 · 5.

Sin embargo, ya no es tan fácil decir de memoria los números primos menores que 100. Aún así no os preocupéis, porque a lo largo de la historia ha habido matemáticos que se han preguntado lo mismo, y afortunadamente, nos han facilitado el problema.

Eratóstenes, matemático, astrónomo y geógrafo griego nacido en el año 276 a.C., ideó un método para filtrar los números compuestos menores que un número natural n dado y quedarnos, por tanto, sólo con los números primos. El algoritmo, llamado la Criba de Eratóstenes, es el siguiente:

1. Crear una lista con los números naturales de 1 hasta n.
2. Sea p el primer número natural no marcado, inicialmente p=2, marcar todos los múltiplos de p.
3. Si p≤√ n  entonces seleccionar el siguiente p y volver al segundo paso. En caso contrario, parar.
4. La lista no marcada el conjunto de números primos menores que n.

Criba de Eratóstenes para n = 100

En realidad, 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. Pero, ¿por qué no seguir tachando números para p mayor de √ n ?

1. Sea $$n$$ un número compuesto entonces $$ n = ab $$ con $$a>1,n>b$$
2. Sea $$ a \leq b $$ entonces $$a^2 \leq ab \rightarrow a^2 \leq n \rightarrow a \leq \sqrt{n} $$
3. Por la propia definición de número primo, $$\forall a$$ existe al menos un factor primo $$p$$ tal que $$p\leq a $$
4. Por tanto podemos decir que $$p\leq a \leq \sqrt{n} \rightarrow p\leq \sqrt{n}$$

La Criba de Eratóstenes es un método lento computacionalmente, ya que la cantidad de memoria que consume 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. Actualmente existen versiones donde se mejora la eficiencia. Una de ellas es la Criba de Atkin, planteada por los matemáticos A. O. L. Atkin y Daniel J. Bernstein, y que consiste, básicamente, en tachar los múltiplos de los cuadrados de los primos.