I would like to compute Chebyshev's function $$ \vartheta(x) = \sum_{p\le x} \log p $$ to within an error of $o(\log x).$ (The estimate $\vartheta(x) \sim x$ has sqrt-error or so even under RH.) What algorithms are available?
Of course one could just enumerate primes and take logarithms, but is there something faster? Possibly using zeta zeros or other techniques.
Here are three algorithms, none great. The first is slow but with great precision. The second is slow and with poor precision. The third is fast with poor precision.
Naive algorithm
Use a standard prime sieve (Atkin-Bernstein or segmented Eratosthenes) to loop over the primes. Take logarithms and sum. Time $\tilde{O}(n),$ space $\tilde{O}(\sqrt n).$ It also parallelizes well.
The error can be selected depending on the precision of the logarithms (which for any reasonable choice will be hidden by the soft-O). AGM iteration would allow on the order of $\sqrt x$ digits (which is pretty excessive) without changing the time or space estimate. This gives error $\exp(-\sqrt x)$ or so. (To be more precise you need to look at the log factors.)
Splitting
Pick some $0<e<1/2$ and split the interval $(x^{1/2+e}, x]$ into $x^e$ intervals of length $x^{1-e}$. At the boundary $y$ of each interval, compute $\pi(y)$. Now you know the number of primes in each interval and can bound the value of $\vartheta(x)$ by $$ \sum_{n=1}^{x^e} (\pi(I_n)-\pi(I_{n-1}))\log(I_{n-1}) \le \vartheta(x) - \vartheta(x^{1/2+e}) \le \sum_{n=1}^{x^e} (\pi(I_n)-\pi(I_{n-1}))\log(I_n) $$ where $$ I_n=x^{1/2+e}+n\frac{x-x^{1/2+e}}{\lfloor x^e\rfloor}. $$
(There are better splittings possible, this is the simplest.)
Time required is $\tilde{O}(x^{1/2+e})$ and space is $\tilde{O}(x^{1/4})$ using the analytic Lagarias-Odlyzko algorithm. The error is approximately $$ \begin{align} &\sum_{n=1}^{x^e}(\pi(I_n)-\pi(I_{n-1}))(\log(I_n)-\log(I_{n-1}))\\ \approx&\sum_{n=1}^{x^e} \frac{\pi(I_n)-\pi(I_{n-1})}{n}\\ \approx&\sum_{n=1}^{x^e} \frac{x^{1-e}}{n\log x}\\ \approx&\frac{x^{1-e}}{\log x}\sum_{n=1}^{x^e} \frac{1}{n}\\ \approx&ex^{1-e}\\ \end{align} $$
Not bothering
Approximate $\vartheta(x)\approx x.$ Time and space are $O(\log x)$, error is $\tilde{O}(\sqrt x)$ on RH.