Conference abstracts
Session S13 - Number Theory
July 26, 15:00 ~ 15:40
La criba de Eratóstenes en menos espacio
Harald Helfgott
Georg-August Universitaet Goettingen/CNRS, Alemania/Francia - harald.helfgott@gmail.com
Digamos que queremos una lista de todos los números primos de $1$ hasta $N$, o factorizar todos los enteros del $1$ hasta $N$. Muchos aprendimos la criba de Eratóstenes en la primaria. Con ciertos trucos estándar, esta criba puede hacerse en espacio aproximadamente $\sqrt{N}$, en vez de $N$. Veremos cómo modificar la criba de Eratóstenes para que funcione en espacio $N^{1/3} (\log N)^{2/3}$ y tiempo aun esencialmente linear en $N$.
La inspiración principal viene de trabajos de índole combinatoria (Voronoi-Sierpinski) sobre el método del circulo; hay en esto una conexión con la versión de Galway (2000) de la criba de Atkin, que también utiliza espacio esencialmente $N^{1/3}$. La ventaja de la criba de Eratóstenes es que se puede utilizar para factorizar o para calcular diversas funciones aritméticas, y no sólo para producir números primos.