La lista que da es una mezcla de métodos de factorización y tamices de números primos. Se abordan mejor en preguntas separadas. Recomiendo Crandall y Pomerance “Prime Numbers: A Computational Perspective” como un buen recurso para ambos. Está disponible en forma impresa o en línea. El documento técnico de Sorenson de 1990 “Introducción a los tamices de números primos” es una descripción general decente de algunos de los problemas, además de brindar detalles técnicos.
Para los números primos, tenemos tres algoritmos principales de tamizado:
- SoE (Tamiz de Eratóstenes). El método más antiguo. Una implementación correcta de las 4 líneas básicas es bastante efectiva. Las implementaciones actuales más rápidas usan formas optimizadas de esto.
- SoA (Tamiz de Atkin). El nuevo método. Bajo ciertos supuestos, tiene la mejor complejidad asintótica. Bernstein (coautor del tamiz) escribió una versión muy optimizada de esto, que es bastante rápida: la tercera a la cuarta más rápida de las que he probado. Se ralentiza a medida que aumenta el tamaño. Más complicado que SoE. Las implementaciones que utilizan pseudocódigo ingenuo de la idea general son bastante más lentas que las implementaciones de SoE simples correctas.
- Tamiz de Sundaram. Interesante pero no se usa generalmente.
El SoA tiene una rueda mod-60 incorporada, por lo que no se consideran los múltiplos de 2, 3 y 5. El SoE se puede modificar trivialmente para omitir múltiplos de 2 o 2 + 3. Las ruedas adicionales requieren un poco más de trabajo, pero es común que las implementaciones usen una rueda mod-30 para saltar también 2 + 3 + 5. He visto implementaciones que usan mod-210 y mod-2310 para omitir aún más los primos pequeños, pero estos son más raros.
Si bien el SoA tiene una buena complejidad asintótica, en la práctica tiene una sobrecarga mayor y requiere un trabajo no trivial para implementarlo adecuadamente. Dada la misma habilidad e inversión de tiempo, el SoE es una mejor opción en mi opinión. Si su argumento para el SoA se basa en la complejidad del tiempo asintótico o en un solo párrafo que encontró en línea, pero su implementación no es la versión completa descrita en el documento, entonces se está engañando a sí mismo.
- ¿Puedes verificar esta prueba elemental propuesta del último teorema de Fermat en la sección de comentarios debajo de esta pregunta?
- Sean a, b, j y k enteros positivos que satisfagan a ^ j = b ^ k, (j, k) = 1. ¿Cómo muestra que a = r ^ k y b = r ^ j para algún entero positivo r?
- ¿Cuál es el resto cuando [matemáticas] 13 ^ {100} + 17 ^ {100} [/ matemáticas] se divide por [matemáticas] 25 [/ matemáticas]?
- Sea [math] d (n) [/ math] el número de divisores de un número natural [math] n [/ math]. ¿Cómo se demuestra que [matemáticas] d (mn) = d (m) d (n) [/ matemáticas] si [matemáticas] mcd (m, n) = 1 [/ matemáticas]?
- ¿Cómo se pueden dividir n enteros en m subconjuntos no vacíos de modo que se minimice la diferencia entre las sumas de subconjuntos máximas y mínimas?
Algunas otras cosas a considerar:
- Presionando. Para segmentos grandes, podemos rellenar previamente la memoria con un patrón que cubre primos pequeños. Este patrón se puede hacer previamente y rotar en su lugar, construido a través de un tamiz pequeño en expansión o un híbrido. Este es un gran ahorro práctico, ya que es fácil de acceder a la memoria. No es raro tener este tamiz 2,3,5,7,11,13,17 con un solo conjunto de memoria.
- ruedas Realmente desea omitir múltiplos de 2, ya que generalmente está bastante claro que la mitad de su trabajo se realiza en números que sabe que son compuestos. Extienda esto a múltiplos de 3 y obtendrá más ahorros. Puede seguir yendo a un número estático o ala Pritchard siga rodando ruedas más grandes. Las implementaciones típicas usan una rueda estática mod-6, mod-30 o mod-210, con mod-30 muy común (en parte porque los 8 puntos encajan perfectamente en un byte).
- Tamiz segmentado frente al monolítico estándar. No es un problema para la generación pequeña (por ejemplo, primos por debajo de un millón), pero es muy importante a medida que avanza, y un elemento imprescindible para 10 ^ 12, por ejemplo. Controla el uso de la memoria y también lo hace correr más rápido. Básicamente, divide el rango en segmentos y tamiza cada uno por separado. Resulta que esta es una muy buena idea.
- Tamiz en un rango. Si bien los ejercicios de programación generalmente tienen una generación de números primos de 1 a n, en la vida real a menudo queremos números primos entre A y B. Deberíamos esperar un rendimiento decente incluso si A = 10 ^ 17 y B = 10 ^ 17 + 10 ^ 6 (esto debería solo toma unos pocos milisegundos). Claramente, esto no va a suceder si intentamos tamizar todos los números a 10 ^ 17. Deberíamos poder tamizar en una ventana. Esto está relacionado pero técnicamente no es lo mismo que el tamizado segmentado.
También hay más optimizaciones y variaciones. primesieve, posiblemente la implementación de tamiz actual más rápida, utiliza tres algoritmos diferentes de Sieve of Eratosthenes internamente, cada uno sintonizado para un rango de tamaño diferente. Por supuesto, el autor está tratando de obtener el mejor resultado absoluto, por lo que la mayoría de las personas podrían no encontrar las diferencias lo suficientemente convincentes. Yo uso una única implementación en la mía, aunque más complicada que las dos primeras que usa.