Supongamos que tengo un número naturaln y quiero una lista (o lo que sea) de todos los números primos hastan.

El clásico algoritmo de tamizado principal se ejecuta enO(n log n) tiempo yO(n) espacio: está bien para idiomas más imperativos, pero requiere una modificación en el lugar de las listas y el acceso aleatorio, de una manera fundamental.

Hay una versión funcional que involucra colas de prioridad, lo cual es bastante hábil: puede consultarloaquí. Esto tiene una mejor complejidad espacial en aproximadamenteO(n / log(n)) (asintóticamente mejor pero discutible a escalas prácticas). Lamentablemente, el análisis del tiempo es desagradable, pero es casiO(n^2) (en realidad, creo que se trataO(n log(n) Li(n)), perolog(n) Li(n) es aproximadamenten)

Asintóticamente hablando, en realidad sería mejor simplemente verificar la primalidad de cada número a medida que lo genera, utilizando la división de prueba sucesiva, ya que eso solo tomaríaO(1) espacio yO(n^{3/2}) hora. ¿Hay una mejor manera?

Editar: Resulta que mis cálculos eran simplemente incorrectos. El algoritmo en el artículo esO(n (log n) (log log n)), que los artículos explican y prueban (y vean la respuesta a continuación), no el complicado desastre que puse arriba. Todavía me gustaría ver una buena feO(n log log n) algoritmo puro si hay uno por ahí.