I need to compute efficiently the sum $$ \sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor. $$
We can do this in $O({\sqrt{n}})$ but I need a faster algorithm: for example, it would be fine an algorithm of complexity $O(\sqrt[3]{n})$ (cube root in time) or $O(\log n)$ whatever, but however less than the square root in time.
edit1:
So far what i have got $$ \sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor= n *\left \lfloor {\sqrt{n}} \right \rfloor - \sum_{i=1}^{i=\left \lfloor {\sqrt{n}} \right \rfloor} n \mod i^{2} $$
Now how can we efficiently compute $$ \sum_{i=1}^{i=\left \lfloor {\sqrt{n}} \right \rfloor} n \mod i^{2} $$
edit2:
We can look at it by taking $\left\lfloor\frac{N}{i^2}\right\rfloor=1$ whenever $1\leq\frac{N}{i^2}<2$. So whenever $\sqrt{N}\geq i>\sqrt{\frac{N}{2}}$. There are $\left\lfloor\sqrt{N}\right\rfloor-\left\lfloor\sqrt{\frac{N}{2}}\right\rfloor$ such values of $i$.Now how can $i^2$ can be multiplied to the above terms.