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 tener una probabilidad compleja o imaginaria? Si es así, ¿qué implicaría eso?
- ¿Cuál es la explicación de la ecuación 1-4.6 en el libro "Cálculo exterior aplicado"?
- ¿Alguien puede probar matemáticamente que la vida es una mezcla de felicidad y tristeza?
- ¿Cuáles son los cinco ejemplos que un estudiante debe encontrar en un curso introductorio de topología?
- ¿Son los patrones en las matemáticas evidencia de la existencia de una fuerza de orden universal no inteligente que uno podría llamar 'dios'?
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.