0

I am new to number theory, I have to find the number of divisors up to $10^9$, but i dont know how to do it efficiently and store it in an array in 'c'. I am using sieve algo to find the number of divisors, here is what I am doing

#include<stdio.h>
#define N 100000
int div[N+1];
void divisors() {
  int i,len,j;
  for(i=2;i<=N;i++) {
     for(j=i;j<N;j+=i)
      div[j]++;
  }
}

int main(){
  int i;
  divisors();
  for(i=1;i<N;i++) printf("%d\n",div[i]+1);
  return 0;
}

Thank You

Cameron Buie
  • 102,994
avinashse
  • 179
  • Every number up to $n$ is a divisor of something. – Git Gud Sep 08 '13 at 17:24
  • Do you mean, given any number up to 10^9, you must list down all its divisors? – markovchain Sep 08 '13 at 17:25
  • @markovchain I have just to tell number of divisors – avinashse Sep 08 '13 at 17:25
  • For each $1<i<j<10^9$, you could check if $j%i\equiv 0$. If so, add $i$ to the array of divisors of $j$ (however you'd like to do that). – Ian Coley Sep 08 '13 at 17:39
  • Do you need all divisor counts, or just the divisor count of some numbers $\leqslant 10^9$? If only some, about how many? – Daniel Fischer Sep 08 '13 at 17:55
  • @DanielFischer Actually I need to find the sum of divisors of all numbers upto 10^9, so I am calculating divisors of all numbers upto 10^9 then I will be taking sum of numbers. – avinashse Sep 08 '13 at 18:18
  • Aha. Sum of number of divisors. Hang on a minute, I'm going to post a link to a dupe. – Daniel Fischer Sep 08 '13 at 18:19
  • 1
    Here it is. Comes up a lot recently. – Daniel Fischer Sep 08 '13 at 18:22
  • @DanielFischer I found there ∑n≤Nd(n)=NlogN+(2γ−1)N+O(sqrt(N)), what that O(sqrt(N)) means, how to calculate that..? – avinashse Sep 08 '13 at 20:28
  • @avinashse $O(\sqrt{N})$ means something bounded by a constant multiple of $\sqrt{N}$. But since you want an exact answer, look at the formula in my answer, that gives a relatively efficient way of computing the number (you can still improve on that, but for the online judges/programming competitions, it ought to be efficient enough when directly translated into code). – Daniel Fischer Sep 08 '13 at 20:33
  • @DanielFischer you mentioned there upto 1000 its efficient,but i ve to compute for upto 10^9. – avinashse Sep 08 '13 at 20:44
  • @DanielFischer And I will be really very thankful if you kindly help me suggesting any easy starting book for number theory along with video tutorials :) – avinashse Sep 08 '13 at 20:45
  • It's efficient for some several thousand queries. If you have many more queries to serve, it becomes more efficient to compute all the sums and look them up - well, you will have memory problems with $10^9$ stored unsigned long long, so you'd have to trade some speed for space. – Daniel Fischer Sep 08 '13 at 20:48
  • See also http://math.stackexchange.com/questions/486864 Considering the amount of questions this has generated lately, I wonder where it comes from. – mrf Sep 08 '13 at 21:20
  • Does this answer your question? How to simplify this summation containing floor – Peter Phipps Jul 14 '22 at 08:03

1 Answers1

1

We are interested in the number of divisors, so first you have to do a prime factorization for every number. We'll take $36091440$ as an example. We can write it as:

$$36091440 = 2^4 \cdot 3^3 \cdot 5 \cdot 7^2 \cdot 11 \cdot 31$$

Now we'll generate all combinations to get all divisors. First for $2$ there are 5 option, we can include $0,1,2,3 \text{ or } 4$ $2$'s in the product that we'll give a divisor. So the number of option is the value of the exponent of the prime factor plus 1.

So this number will have:

$$5 \cdot 4 \cdot 2 \cdot 3 \cdot 2 \cdot 2 = 480$$

So there will be $480$ divisors.

Note that we calculate the option when none of the prime factors is included into the product, because also $1$ is a divisor of any number.

Stefan4024
  • 35,843