can you explain it with example…
“there are only sqrt(n) different values for [n/i] over all i from 1 to n”
Take n=8
For i=1 to 8,
[n/i] takes values 8,4,2,2,1,1,1,1 which are only 4 distinct values.
Its actually about 2*sqrt(n) because for i= 1 to sqrt(n) you take values incrementing from 1 to sqrt(n).
After this you go from the rear and take values in chunks having same [n/i].
In this example, you dont iterate over all i from 5-8. You take that as a whole chunk with common [n/i].
Check out editorial for details/