Computing sums of divisors in $O(\sqrt n)$ time?
Solution 1:
You are looking for $p_n = \sum_{k=1}^n d(k)$, where $d(k)$ is the number of divisors of $k$.
This paper claims an algorithm running in $O(n^{1/3})$ time and $O(\log n)$ space. See also Deterministic methods to find primes by Tao, Croot Ill and Helfgott sprung from a Polymath project.
Note that formula (4) in the first link gives a simple $O(\sqrt n)$ algorithm:
$$p(n) = 2\sum_{k=1}^{\lfloor\sqrt{n} \rfloor} \left\lfloor\frac{n}{k} \right\rfloor- \lfloor\sqrt n \rfloor^2$$