how to sum the floors of ratios n/k when prime factorization of n is known 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:

*If $n=p^{2^k}$ then $n\Pi_{i=0}^k(1+p^{-2^i})$ sums for all combinations of factors from $p^0$ to $p^{2^k}$

*If $n=4!=24$ then $$\sum_{k=2}^{n-1}\Bigl\lfloor \frac nk\Bigr\rfloor=12+8+6+\Bigl\lfloor \frac {24}5\Bigr\rfloor+4*(6-5)+3*(8-6)+2*(12-8)+1*(24-12)$$ So the biggest region of uncertainty for a factorial $f!$ lies between $f<k<(f-1)!$.  Furthermore we have $$((f-1)!-1)((f-1)!-f-1) < \sum_{k=f+1}^{(f-1)!-1}\Bigl\lfloor \frac nk\Bigr\rfloor < f((f-1)!-f-1)$$ 
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})
$$
 A: 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}
$$
