Cómo generar los primeros números primos [matemáticos] n [/ matemáticos], en lugar de generar todos los números primos menores que [matemáticos] n [/ matemáticos] utilizando el tamiz de Eratóstenes

Ejecute la versión del Tamiz de Eratóstenes que se describe en este documento: Página en hmc.edu

(No estoy de acuerdo con la afirmación hecha en ese documento de que el ingenuo Haskell one-liner presentado a menudo para este propósito no también merece ser considerado una implementación del tamiz de Eratóstenes, pero no obstante el documento presenta un enfoque eficiente para exactamente el problema Estas interesado en)

Suponiendo que no está tratando con valores trivialmente pequeños de n, use un límite superior para el enésimo primer, tamice hasta allí, luego ignore o elimine los valores adicionales. No desea una estimación , sino un límite superior (es decir, un valor tal que el enésimo real siempre sea menor o igual que él), para asegurarse de que siempre tamice al menos el lugar adecuado.

Podrías usar el simple

unsigned long upper=n*(log(n)*log(log(n)));

que sobreestima mucho, o se vuelve más elegante para los límites más estrechos. Por ejemplo:

doble fn = (doble) n;
doble flogn = log (fn);
doble flog2n = log (flogn);
UV nth_prime = / * Dusart 2010 para> 179k, personalizado para 18-179k * /
(n> = 688383)? (UV) ceil (fn * (flogn + flog2n-1.0 + ((flog2n-2.00) / flogn))):
(n> = 178974)? Techo (UV) (fn * (flogn + flog2n-1.0 + ((flog2n-1.95) / flogn))):
(n> = 18)? Techo (UV) (fn * (flogn + flog2n-1.0 + ((flog2n + 0.30) / flogn)))
: 59;

no desperdicia demasiado. Para darle una idea de qué tan bien funciona, pedir el primer millón de primos significa que el último es 15,485,863. La función anterior significa que tamizamos a 15,486,599, solo 736 demasiado lejos. Con 10 millones tamizamos un 0.01% más de lo necesario. Hay límites aún mejores (por ejemplo, Axler 2013 para n> = 8009824).

También podría usar lo que a veces se denominan tamices extensibles: tamices que mantienen el estado de manera que pueda conseguir que sigan bombeando valores de manera eficiente. A menudo son más lentos o más complicados (estoy seguro de que algunos harán excepciones a esto en general, y como todos los problemas de ingeniería, la respuesta es “depende”).

Lo anterior es un poco diferente de usar un tamiz segmentado para generar bloques a la vez. Siempre podemos usar un tamiz segmentado, incluso si conocemos los límites completos (son más rápidos una vez que superan un cierto tamaño, y queremos uno para la generación eficiente de rango independientemente).

Wikipedia sugiere que [math] \ frac {x} {\ log x + 2} <\ pi (x) [/ math] se cumple para [math] x \ geq 55 [/ math]. (Ver este enlace: http://en.wikipedia.org/wiki/Prime_number_theorem#Bounds_on_the_prime-counting_function ). Entonces, lo que tiene que hacer es lo siguiente: Dada una [matemática] n [/ matemática] encuentre algunas [matemáticas] x [/ matemática] pequeñas de manera que [matemática] \ frac {x} {\ log x +2}> n [/matemáticas]. Entonces se garantiza que tiene [números matemáticos]> n [/ matemáticas] números primos por debajo de [matemáticas] x [/ matemáticas] y puede realizar su algoritmo para encontrar números primos debajo de [matemáticas] x [/ matemáticas]. Por supuesto, encontrará demasiados, pero simplemente descarte el resto.

No puede predecir dónde está el próximo número primo, por lo que no hay una forma exacta de hacer lo que quiere. Puedes acercarte usando la fórmula que estima el número de primos. Elija un tamaño de matriz 10% más grande y eso podría funcionar. O si se queda corto, vuelva a hacerlo solo comenzando justo después del último tamaño de matriz.

Nadie sabe exactamente dónde está el enésimo primer. Tenemos estimaciones de dónde está, pero una suposición no lo ayudará si es demasiado pequeño. Pero, si puede obtener un límite superior, puede tamizar hasta que tenga tantos números primos como esperaba encontrar.

El teorema de Rosser establece que la enésima prima está garantizada a ser menor que [matemática] n \ log n + n \ log \ log n [/ matemática] cuando n es mayor que 6. Por lo tanto, su mejor opción es tamizar hasta esto valor, y pare una vez que tenga n primos.