Search code examples
number-theory

How to find total number of divisors upto N?

Given a number N, have to find number the divisors for all i where i>=1 and i<=N. Can't figure it out.Do I have to this using prime factorization? Limit is N<=10^9 Sample Output:

1 --> 1
2 --> 3
3 --> 5
4 --> 8
5 --> 10
6 --> 14
7 --> 16
8 --> 20
9 --> 23
10 --> 27
11 --> 29
12 --> 35
13 --> 37
14 --> 41
15 --> 45
Solution

  • To compute much faster, use the following Pseudocode:

    sum = 0; u = floor(sqrt(N)); foreach k <= u, sum += Floor(N / K); sum = 2*sum-u*u

    The above formula is given by Peter Gustav Lejeune Dirichlet in 19th Century.

    I have written a C program using above algorithm and it takes 0.118 second on my computer to compute sum of number of divisors from 1 upto 10^14. The answer is 3239062263181054.