I want to calculate the sum


$$ 
\sum\_{i=1}^{n} \left\lfloor\frac{n}{i}\right\rfloor,
$$


and it seems to require to calculate the sum
$$
\sum\_{i=1}^{n} (n \bmod i).
$$


How can I get an $O(1)$ solution instead of the $O(n)$ solution?



How can I calculate $ \sum_{i=1}^{n} (n \bmod i) $
You're probably not going to be able to compute $\sum\_{1 \leq i \leq n} n \bmod i$ efficiently. Let $f(n)$ denote this sum. This is sequence A004125 in Sloane's Online Encyclopedia of integer sequences (see <http://oeis.org/A004125> ). It is known and relatively simple to prove that $f(n) = n^2 - \sum\_{1 \leq i \leq n} \sigma(i)$, where $\sigma$ is the sum of divisors function.


So if you could compute $f(n)$ efficiently, then (by considering $f(n)-f(n-1)$), you'd be able to compute $\sigma(n)$ efficiently. But an old result of mine (with Gary Miller and Eric Bach, in SIAM J. Computing in 1986), computing $\sigma(n)$ is random-polynomial-time equivalent to factoring $n$. So unless there is an efficient algorithm for factoring...


Also, as Emil points out, $g(n) = \sum\_{1 \leq i \leq n} \lfloor n/i \rfloor$ equals $\sum\_{1 \leq i \leq n} \tau(i)$, where $\tau$ is the number of divisors function. An efficient algorithm for $g(n)$ would allow fast computation of $\tau(n)$, and nobody knows how to compute $\tau(n)$ efficiently, either. 


In everything I said above, "efficiently" means polynomial time in $\log n$.


By the way, S. Carnahan's answer is correct, but you and he are using different computational models. You seem to want to use the unit-cost model, which is not appropriate when dealing with computations involving integers. 


