¿Cuál es la fórmula matemática para hallar la suma de los 1000 primeros números primos?

Question

Estoy tratando de mejorar mis habilidades de codificación en codeeval (haciendo problemas de práctica).

Una de las preguntas de programación que tengo que responder es escribir un código que sume los 1000 primeros números primos.

¿Cuál es la fórmula matemática para hallar la suma de los 1000 primeros números primos?

Answer 1

Si existiera una fórmula cerrada $f(n)$ que da la suma de los primeros $n$ números primos, entonces $g(n)=f(n)-f(n-1)$ sería una fórmula de forma cerrada para el $n^{\textrm{th}}$ de primera. Por desgracia, no existe tal fórmula.

Answer 2

Tienes que encontrar el k-ésimo primo (un problema de programación razonable) y simplemente sumar los 1000 primeros.

Answer 3

Puedo pensar en ello en términos de algoritmo, no esencialmente de fórmula.

Una forma muy interesante de hacerlo es el Tamiz de Eratóstenes, y su algoritmo tiene el siguiente aspecto:

Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., √n :
  if A[i] is true:
    for j = i2, i2+i, i2+2i, ..., n:
      A[j] := false

Now all i such that A[i] is true are prime.

Answer 4

Sum(n)= 2+ Σ k=5 a n [(e(2πi(k-1)!/k)-1]/[e(-2πi/k)-1] esto te da la suma de todos los números primos para n=5 o superior

Espero que esté claro. Escríbelo prestando atención a todos los ()

Answer 5

Tengo un pregunta anterior planteando una forma más general de esta cuestión, en la que permito elevar los primos a una potencia arbitraria ( $k=1$ aquí). Esta respuesta da un algoritmo eficiente para calcular la suma de los primos hasta un límite dado mod un arbitrario $m$ .

El algoritmo no sería eficiente si eliges $m$ muy grande, así que en su lugar ejecute el algoritmo repetidamente con muchos valores coprimos pequeños de $m$ y reconstruir la respuesta con el Teorema Chino del Resto.

Ahora ya sabes cómo hallar la suma de los primos hasta $N$ así que todo lo que necesitas es encontrar un número $N$ que es al menos tan grande como el primo 1000 pero más pequeño que el primo 1001. Puedes hacerlo con la Criba de Eratóstenes, como se menciona en otras respuestas, o con el algoritmo Deléglise-Dusart-Roblot utilizado en los pasos anteriores.

¿Lo veis? Todo lo que necesitas para terminar esta tarea son conocimientos de matemáticas a nivel de investigación y la implementación de un algoritmo complejo que (que yo sepa) todavía no se ha escrito nunca.

Por supuesto, podrías encontrar los 1000 primeros primos y sumarlos. Esto es asintóticamente ineficiente, pero tarda alrededor de un milisegundo en este tamaño del problema. También puedes buscar A007504 en la OEIS, donde encontrará directamente la respuesta.