Para tamices monolíticos, ciertamente podemos. Sin embargo, hemos pasado el punto en el que los tamices segmentados son lo correcto. He comparado varios SoE y tengo resultados para 10 ^ 11 para siete tamices monolíticos. Varían en el tiempo de 1,5 minutos a 7 minutos. Los más simples (por ejemplo, aproximadamente 20 líneas con el clásico tamiz real de 4 líneas) usan 1 bit por número impar, es decir, aproximadamente 6.25GB. Algunos de ellos usan el popular método mod-30 que usa 8 bits por 30 valores, lo que significa aproximadamente 3.3GB. Esos son un poco más complicados, pero no tan horriblemente. Mod-6 (omitiendo múltiplos de 2 y 3 en lugar de solo 2 o 2,3,5) también es posible y hay un buen tamiz de Python que lo usa.
Por lo general, queremos usar un tamiz segmentado. Esto no solo funciona sustancialmente más rápido, sino que usa una cantidad de memoria enormemente menor. Una buena reseña está en el sitio de Kim Walisch: tamiz segmentado de Eratóstenes
Generar números primos a 10 ^ 11 requiere menos de 1 MB (suponiendo que hagamos algo con cada uno y luego pasar al siguiente) y tan poco como 20 segundos (más típicamente 30-60). Con los mejores primos de software, se pueden hacer 10 ^ 13 en menos de una hora, y algunos otros lo hacen en menos de 2 horas. El tamiz segmentado de Atkin realmente se está desacelerando en este punto y lleva más de 3 horas.
- ¿Es posible aplicar una transformación a un fractal arbitrario para obtener una función diferenciable aproximada de ese fractal a cierta profundidad?
- ¿Cómo podemos resolver la relación de recurrencia: [math] a_n \ in \ mathbb {C}: [/ math] [math] a_ {n + 1} = a_n ^ 2-n [/ math]?
- ¿Cuál es la diferencia entre un infinito y un número cardinal?
- ¿Cómo explicarías el impulso, la respuesta al impulso y la convolución usando ejemplos físicos?
- Si los humanos estuvieran alineados uno detrás del otro, en el hombro, ¿cuántas veces circunnavegarían el ecuador?
Una vez en los tamaños bastante grandes de 10 ^ 17 y más, las cosas comienzan a ser un poco más interesantes. Hay algunas soluciones que he visto.
- Continúe usando el SoE segmentado estándar. Poca memoria e incluso podríamos reducirla aún más agregando otra capa (entonces [math] O (n ^ {. 25}) [/ math] en lugar de [math] O (n ^ {. 5}) [/ math]) , aunque nunca he visto a nadie meterse en problemas. Comienza a volverse bastante lento, especialmente si nuestros segmentos son cortos.
- Usa el tamiz amigable de caché de Tomás Oliveira e Silva. Muy rápido una vez dentro de este rango, y muy popular para proyectos computacionales (por ejemplo, búsqueda de Goldbach, búsqueda de primer espacio, tamiz “grande” de primesieve). Una gran desventaja es que la memoria auxiliar crece rápidamente, por lo que estamos de vuelta en el rango de 3+ GB, aunque no estamos escaneando todo eso en cada iteración.
- Tamiz híbrido / primalidad. Sabemos que el tamiz es excelente como método de división de prueba en masa. Sabemos que BPSW o Miller-Rabin de 7 bases es completamente determinista para todas las entradas de 64 bits y puede ejecutarse bastante rápido. Por lo tanto, tamizamos hasta un valor razonablemente grande y luego dejamos que la prueba de primalidad verifique todo lo que queda (que son primos o tienen factores muy grandes). Si esto es más rápido depende tanto del tamaño de entrada (por ejemplo, el número de bits que impacta la profundidad necesaria), el rango (cuántos números está sobrepasando nuestro tamizado) y las velocidades relativas del tamiz y la prueba de primalidad.
Un último comentario, que a veces nuestro problema no requiere tamizado. Por ejemplo, se puede contar primos hasta n sin generar la mayoría de ellos. También es estúpidamente más rápido. Puede sumar números primos de manera similar, haciendo posibles cosas como el recuento exacto de números primos hasta 10 ^ 26 o encontrando la suma exacta de todos los números primos menores que 10 ^ 25. Esto simplemente no es práctico mediante tamizado.
