Can anyone help me with references to the current fastest algorithms for counting the exact sum of primes less than some number n? I'm specifically curious about the best case running times, of course. I'm pretty familiar with the various fast algorithms for prime counting, but I'm having a harder time tracking down sum of prime algorithms...



Fastest algorithm to compute the sum of primes?
Deléglise-Dusart-Roblot [1] give an algorithm which determines $\pi(x,k,l)$, the number of primes up to $x$ that are congruent to $l$ modulo $k,$ in time $O(x^{2/3}/\log^2x).$ Using this algorithm to count the number of primes in all residue classes $k<2\log x$ takes
$$1+\sum\_{p<2\log x}(p-2)\sim\frac{2\log^2x}{\log\log x}$$
invocations of Deléglise-Dusart-Roblot for a total of $O(x^{2/3}/\log\log x)$ time.


This allows one to determine the value of $\sum\_{p\le x}p$ mod all primes up to $2\log x$ and hence, by the Prime Number Theorem and Chinese Remainder Theorem, the value of the sum mod $\exp(\vartheta(2\log x))=x^2(1+o(1)).$ Together with bounds on the value of $\sum\_{p\le x}p$ [2], this allows the computation of the sum.


Note that the primes slightly beyond $2\log x$ may be required depending on the value of $\vartheta(2\log x).$ Practically speaking, except for $x$ tiny, $2\log x+\log x/\log\log x$ suffices. This does not change the asymptotics.


I do not know if it is possible to modify the Lagarias-Odlyzko analytic formula [3] to count in residue classes. If so, this would allow an $O(x^{1/2+o(1)})$ algorithm.


References
==========


[1] Marc Deléglise, Pierre Dusart, and Xavier-François Roblot, [Counting primes in residue classes](http://www.ams.org/journals/mcom/2004-73-247/S0025-5718-04-01649-7/S0025-5718-04-01649-7.pdf), *Mathematics of Computation* **73**:247 (2004), pp. 1565-1575. [doi 10.1.1.100.779](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.779)


[2] Nilotpal Kanti Sinha, [On the asymptotic expansion of the sum of the first n primes](http://arxiv.org/abs/1011.1667) (2010).


[3] J. C. Lagarias and A. M. Odlyzko, [Computing $\pi(x)$: An analytic method](http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf), *Journal of Algorithms* **8** (1987), pp. 173-191.


