According to @harald-hanche-olsen the sum of the floors of ratios of $n/k$ is approximately:
$$n(\ln n-1-\ln2)<\sum_{k=2}^{n-1}\Bigl\lfloor \frac nk\Bigr\rfloor<n\ln n.$$
If the prime factorization of $n$ is known (that is, if $n=\Pi_i{k_i^{\alpha_i}}$), can a closer approximation be obtained?
In my case the exact value of $n$ is not important, just the accuracy of the sum of the floors of the ratios. One approach is to let $n=\Pi^p_i{i}$ so the the first $p$ sums would be exact (equal to $nH_p$ where $H_p$ is the $p^{th}$ harmonic number) and the approximation is needed only for:
$$ \sum_{k=p+1}^{n-1}\Bigl\lfloor \frac{\Pi^p_i{i}}k\Bigr\rfloor $$
The reduction in the range is marginal using this approach: it can be expressed as: $$nH_p+n(\ln n-1-\ln2)-p(\ln p-1-\ln2)\le\sum_{k=2}^{n-1}\Bigl\lfloor \frac nk\Bigr\rfloor\le nH_p+n\ln n-p\ln p.$$
Other optimizations may be possible. For example:
Edit
The answer should be in the form of:
Given:
$$ a_v <= \sum_{k}^{v-1}\Bigl\lfloor \frac{v}k\Bigr\rfloor <= a_v+\mathcal{O}(\sqrt{v})\\ a_u <= \sum_{k}^{u-1}\Bigl\lfloor \frac{u}k\Bigr\rfloor <= a_u+\mathcal{O}(\sqrt{u}) $$
Conclusion: a method exists to compute $a_{uv}$ such that: $$ a_{uv} <= \sum_{k}^{uv-1}\Bigl\lfloor \frac{uv}k\Bigr\rfloor <= a_{uv} + \xi \text{ where } \xi << \mathcal{O}(\sqrt{uv}) $$
Asymptotic Estimate
First, we have $$ \sum_{k=1}^n\frac nk=n\log(n)+\gamma n+\frac12+O\left(\frac1n\right)\tag{1} $$ Using Riemann Sums, we have $$ \begin{align} \lim_{n\to\infty}\sum_{k=1}^n\left\{\frac nk\right\}\frac1n &=\int_0^1\left\{\frac1x\right\}\,\mathrm{d}x\\ &=\sum_{k=1}^\infty\int_{\frac1{k+1}}^{\frac1k}\left(\frac1x-k\right)\,\mathrm{d}x\\ &=\lim_{n\to\infty}\sum_{k=1}^{n-1}\left[\log\left(\frac{k+1}k\right)-\frac1{k+1}\right]\\[9pt] &=\lim_{n\to\infty}[\,\log(n)-(H_n-1)\,]\\[12pt] &=1-\gamma\tag{2} \end{align} $$
Bounding the Error in $\boldsymbol{(2)}$
We will consider three classes of intervals:
$\left[\frac n{k+1},\frac nk\right]$ where $k\lt\sqrt{n}$.
$\left[\frac n{k+1},\frac nk\right]$ where $k\ge\sqrt{n}$ which contain an integer.
$\left[\frac n{k+1},\frac nk\right]$ where $k\ge\sqrt{n}$ which don't contain an integer.
There are fewer than $\sqrt{n}$ intervals of class 1.
The integers contained in the intervals of class 2 must be at most $\sqrt{n}$. Thus, there are at most $\sqrt{n}$ intervals of class 2.
For all intervals of class 1 and 2, $$ \begin{align} \left|\frac1n\left\{\frac{n\vphantom{1}}k\right\}-\int_{\frac kn}^{\frac{k+1}n}\left\{\frac1x\right\}\,\mathrm{d}x\right| &\le\int_{\frac kn}^{\frac{k+1}n}\left|\left\{\frac{n\vphantom{1}}k\right\}-\left\{\frac1x\right\}\right|\,\mathrm{d}x\\ &\le\frac1n\tag{4} \end{align} $$
For intervals of class 3 and $\frac kn\le x\le\frac{k+1}n$ $$ 0\le\left\{\frac{n\vphantom{1}}k\right\}-\left\{\frac1x\right\}\le\left\{\frac n{k\vphantom{+}}\right\}-\left\{\frac n{k+1}\right\}=\frac n{k(k+1)}\tag{5} $$ Thus, $$ \begin{align} \frac1n\left\{\frac{n\vphantom{1}}k\right\}-\int_{\frac kn}^{\frac{k+1}n}\left\{\frac1x\right\}\,\mathrm{d}x &=\int_{\frac kn}^{\frac{k+1}n}\left(\left\{\frac{n\vphantom{1}}k\right\}-\left\{\frac1x\right\}\right)\,\mathrm{d}x\\ &\le\frac1{k(k+1)}\tag{6} \end{align} $$ Summing the contribution from intervals of class 1 and 2, using $(4)$, and the contribution from intervals of class 3, using $(6)$,we get $$ \left|\sum_{k=1}^n\left\{\frac nk\right\}\frac1n-\int_0^1\left\{\frac1x\right\}\,\mathrm{d}x\right|\le\frac3{\sqrt{n}}\tag{7} $$
Final Result
Combining $(1)$, $(2)$, and $(7)$, we have $$ \begin{align} \sum_{k=1}^n\left\lfloor\frac nk\right\rfloor &=\sum_{k=1}^n\left(\frac nk-\left\{\frac nk\right\}\right)\\ &=n\log(n)+(2\gamma-1)n+O(\sqrt{n})\tag{8} \end{align} $$ Subtracting $n+1$, we get $$ \bbox[5px,border:2px solid #C0A000]{\sum_{k=2}^{n-1}\left\lfloor\frac nk\right\rfloor =n\log(n)-2(1-\gamma)n+O(\sqrt{n})}\tag{9} $$