Tras una semana de ausencia, llega una nueva entrega de la serie sobre números primos. Hoy hablaremos de algoritmos para extraer, de forma gráfica, todos los números primos por debajo de un umbral dado.
Esta vez no habrá densos teoremas ni fórmulas matemáticas, ya que se trata de dos algoritmos muy sencillos y antiguos: la Criba de Eratóstenes y la Criba de Euler. En algunos textos se usa la expresión ‘tamiz’ o ‘filtro’ en vez de ‘criba’. Viene a ser lo mismo.
La Criba de Eratóstenes
Se trata de un algoritmo eficiente para calcular los primos hasta el orden de 107 (es decir, diez millones). Su filosofía es muy sencilla, se basa en ir tachando los números compuestos hasta que en un momento dado podemos garantizar que todos los que quedan son primos.
Eratóstenes nació en Cyrene (Libia) en el año 276 a. C. Trabajó en diversos campos como la astronomía, la historia, la literatura y las matemáticas. Estudió en Alejandría y Atenas, y alrededor del año 255 a. C fue el tercer director de la Biblioteca de Alejandría.
