I am trying to improve my coding skills at codeeval (doing practice problems).
One of the programming questions I have to answer is to write code that will sum the first 1000 prime numbers.
What is the mathematical formula to find the sum of the first 1000 prime numbers?
If there were a closed-form formula $f(n)$ that yields the sum of the first $n$ prime numbers, then $g(n)=f(n)-f(n-1)$ would be a closed-form formula for the $n^{\textrm{th}}$ prime. Alas, no such formula exists.
You have to find the kth prime (a reasonable programming problem) and just add the first 1000 together.
I can think of it in terms of an algorithm, not essentially a formula.
A very interesting way to do so is the Sieve of Erathosthenes, and its algorithm looks like the following:
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.
I have an earlier question asking a more general form of this question, where I allow primes to be raised to an arbitrary power ($k=1$ here). This answer gives an efficient algorithm for computing the sum of the primes up to a given bound mod an arbitrary $m$.
The algorithm would not be efficient if you chose $m$ very large, so instead run the algorithm repeatedly with many small coprime values of $m$ and reconstruct the answer with the Chinese Remainder Theorem.
Now you know how to find the sum of the primes up to $N$, so all you need is to find a number $N$ which is at least as large as the 1000-th prime but smaller than the 1001-st prime. You can do that with the Sieve of Eratosthenes, as mentioned in other answers, or with the Deléglise-Dusart-Roblot algorithm used in the earlier steps.
You see? All you need to finish this homework assignment is an understanding of research-level mathematics and an implementation of a complex algorithm which (to my knowledge) has never yet been written.
Of course, you could just find the first 1000 primes and add them. This is asymptotically inefficient but takes about a millisecond at this problem size. You could also look up A007504 in the OEIS where you will find the answer directly.
Sum(n)= 2+ Σ k=5 to n [(e(2πi(k-1)!/k)-1]/[e(-2πi/k)-1] this gives you the sum of all prime numbers for n=5 or above
Hope it's clear. Write it down paying attention to all the ()
