How to sum sequence?

Question

How can I sum the following sequence:

⌊n/1⌋ + ⌊n/2⌋ + ⌊n/3⌋ + ... + ⌊n/n⌋

This is simply O(n) solution on C++:

#include <iostream>
int main()
{
   int n;
   std::cin>>n;
   unsigned long long res=0;
   for (int i=1;i<=n;i++)
   {
      res+= n/i;
   }
   std::cout<<res<<std::endl;
   return 0;
}

Do you know any better solution than this? I mean O(1) or O(log(n)). Thank you for your time :) and solutions

Edit: Thank you for all your answers. If someone wants the solution O(sqrt(n)): Python:

import math
def seq_sum(n):
 sqrtn = int(math.sqrt(n))
 return sum(n // k for k in range(1, sqrtn + 1)) * 2 - sqrtn ** 2
n = int(input())
print(seq_sum(n))

C++:

#include <iostream>
#include <cmath>
int main()
{
   int n;
   std::cin>>n;
   int sqrtn = (int)(std::sqrt(n));
   long long res2 = 0;
   for (int i=1;i<=sqrtn;i++)
   {
      res2 +=2*(n/i);
   }
   res2 -= sqrtn*sqrtn;
   std::cout<<res2<<std::endl;
   return 0;
}

Answer 1

This is Dirichlet's divisor summatory function D(x). Using the following formula (source)

where

gives the following O(sqrt(n)) psuedo-code (that happens to be valid Python):

def seq_sum(n):
  sqrtn = int(math.sqrt(n))
  return sum(n // k for k in range(1, sqrtn + 1)) * 2 - sqrtn ** 2

Notes:

• The // operator in Python is integer, that is truncating, division.
• math.sqrt() is used as an illustration. Strictly speaking, this should use an exact integer square root algorithm instead of floating-point maths.

Answer 2

Taken from the Wikipedia article on the Divisor summatory function,

where . That should provide an time solution.

EDIT: the integer square root problem can also be solved in square root or even logarithmic time too - just in case that isn't obvious.