How to find total number of divisors upto N?

Question

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

Answer 1

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.

Answer 2

if you want to find the sum of all divisors up to a given N, you don't need any factoring. You can do it (for example) in this way, with a unique loop. Start with 2, 2 is a divisor of 2*2, 3*2, 4*2 and so on. This gives the idea behind.

Foreach k < N, Floor(N / k) is the number of how many times k is a divisor of something < N.

Pseudocode:
sum = 0; foreach k <= N sum += Floor(N / K)

Note that this is not the same thing like asking for the number of divisors of a given N.

Answer 3

Not sure what language you're using, but here's the basic idea:

dim myCount as integer = 1
dim N as integer = 10000000000 '10,000,000,000

For i as integer = 2 to N
   If N mod i = 0 Then
      myCount += 1
   End If
Next i

Notes:

• Mod gives you the remainder of division. So for example:
• 10 mod 1 = 0 (because 1 goes into 10 10-times exactly)
• 10 mod 2 = 0 (...
• 10 mod 3 = 1 (because 3 goes into 10 3-times, with a remainder of 1)
• 10 mod 4 = 2 (because 4 goes into 10 2-times, with a remainter of 2)

You only want to count the results where N mod i = 0, because those are the only instances where i goes into N with no remainder; which I think is what your teacher probably means when they say 'divisor' -- no remainder.

The variable declarations (dim...) and the For loop might be written slightly differently in whatever language you're using. The code above is VB. But if you look in your book index, you'll probably find your language's version of these two common features.

EDIT

OK -- in that case, just add another FOR loop, as follows:

dim myCount as integer = 1
dim N as integer = 10000000000 '10,000,000,000

For i as integer = 1 to N
   For j as integer = 2 to i
      If i mod j = 0 Then
         myCount += 1
      End If
   Next j
Next i