1

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
PEIN
  • 308
  • 1
  • 5
  • 17
  • Home work question? Puzzle question? – aartist Sep 06 '11 at 17:11
  • 1
    If you don't care about efficiency you can just loop through each number and see if its modulus is zero. If so it is a divisor – Richard Sep 06 '11 at 17:19
  • 1
    Already Answered here: http://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number – Richard Sep 06 '11 at 17:21
  • It's not a homework. It's a algorithmic problem. I can easily solve it by the method you stated. But in this case I need some optimization or a closed form answer. – PEIN Sep 06 '11 at 17:45

3 Answers3

12

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.

P L Patodia
  • 166
  • 1
  • 4
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.

Stephan
  • 41,764
  • 65
  • 238
  • 329
emilio
  • 71
  • 1
  • 9
0

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
Chains
  • 12,541
  • 8
  • 45
  • 62
  • maybe I stated the problem wrongly. What I meant was from 1 to N, for each number you have to find number of divisors of that number. Then add all the number of divisor to get the total number of divisors. For example for N=3, answer is 1+2+2=5. 1 for 1, 2 for 2, 2 for 3. These are number of divisor from 1 to 3. So total is 5. And also I can't compute 10^9 within 1 sec. So it has to something efficient. – PEIN Sep 06 '11 at 17:33
  • @caso -- OK -- I just didn't read it carefully -- I edited my answer for that case. – Chains Sep 06 '11 at 17:37
  • I understand the code fine but as I said I can't compute to N since N is 10^9 and it'll take more than 1 sec. I have to answer it within 1 sec. – PEIN Sep 06 '11 at 17:38
  • @caso -- I take that back -- how is it that N = 3 has 5 divisors? What are they? – Chains Sep 06 '11 at 17:39
  • @caso -- nevermind. If you're into the performance to that degree, richard's comment on your original question (the link there) gets into that. – Chains Sep 06 '11 at 17:41
  • it's a sum. From 1 to N, for each number like if N is 5 then 1,2,3,4,5. For each of these 5 numbers you have find number of divisors. Which is 1->1,2->2,3->2,4->3,5->2. So the answer becomes 1+2+2+3+2=10. – PEIN Sep 06 '11 at 17:43