# Sums of sum of divisors in sublinear time [tag:number-theory] [tag:code-golf] [tag:restricted-complexity] [tag:math]

Given a number \$n\$, we have its sum of divisors, \$\sigma(n)\ = \sum_{d | n} {d}\$, that is, the sum of all numbers which divide \$n\$ (including \$1\$ and \$n\$). For example, \$\sigma(28) = 1 + 2 + 4 + 7 + 14 + 28 = 56\$. This is OEIS [A000203](https://oeis.org/A000203).

We can now define the sum of sum of divisors as \$S(n) = \sum_{i=1}^{n}{\sigma(i)}\$, the sum of \$\sigma(i)\$ for all numbers from \$1\$ to \$n\$. This is OEIS [A024916](https://oeis.org/A024916).

Your task is to calculate \$S(n)\$, **in time sublinear in \$n\$, \$o(n)\$**.

# Test cases
```
10 -> 87
100 -> 8299
123 -> 12460
625 -> 321560
1000 -> 823081
1000000 (10^6) -> 822468118437
1000000000 (10^9) -> 822467034112360628
```

# Rules

- **Your complexity must be \$o(n)\$**. That is, if your code takes time \$T(n)\$ for input \$n\$, you must have \$\lim_{n\to\infty}\frac{T(n)}n = 0\$. Examples of valid time complexities are \$O(\frac n{\log(n)})\$, \$O(\sqrt n)\$, \$O(n^\frac57 \log^4(n))\$, etc.
- You can use any reasonable I/O format.
- Note that due to the limited complexity you can't take the input in unary nor output in it (because then the I/O takes \$\Omega(n)\$ time), and the challenge might be impossible in some languages.
- Your algorithm should in theory be correct for all inputs, but it's fine if it fails for some of the big test cases (due to overflow or floating-point inaccuracies, for example).
- [Standard loopholes](https://codegolf.meta.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default) are disallowed.

This is code golf, so the shortest answer wins.