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.

View abstract PDF