Auto comment: topic has been updated by MonsieurV (previous revision, new revision, compare).

Divisor Summatory Function

Let $$$S[n]$$$ be $$$F[1]+F[2]+..+F[n]$$$. Notice that $$$F[a]+F[a+1]+..+F[b]=S[b]-S[a-1]$$$ Now the problem is reduced to computing $$$F[n]$$$. Notice that for a fixed number $$$x$$$ divisors come in pairs (denote them $$$d$$$ and $$$x/d$$$, $$$d<=x/d$$$) Notice that $$$d<=sqrt(x)$$$ thus if $$$x<=n$$$, $$$d<=sqrt(n)$$$. You can fix all numbers $$$d<=sqrt(n)$$$ and you can count how many numbers $$$x<=n$$$ for which also $$$d<=x/d$$$ holds to not count twice. This is just something like $$$2*(n/d-d)+1$$$. $$$(n/d)$$$ is how many numbers divide $$$d$$$, excluding the ones for which $$$x/d<=d$$$, multiplied by 2 to also count $$$x/d$$$ and finally adding 1 to count $$$d$$$ as a divisor of $$$d*d$$$ once. Finally, you have an $$$O(sqrt(b))$$$ solution.