I don't need to list all proper divisors, I just want to get its sum. Because for a small number, checking all proper divisors and adding them up is not a big deal. However, for a large number, this would run extremely slow. Any idea?

Chan Nguyen


8 Answers 8


If the prime factorization of $n$ is $$n=\prod_k p_k^{a_k},$$ where the $p_k$ are the distinct prime factors and the $a_k$ are the positive integer exponents, the sum of all the positive integer factors is $$\prod_k\left(\sum_{i=0}^{a_k}p_k^i\right).$$

For example, the sum of all of the factors of $120=2^3\cdot3\cdot5$ is $$(1+2+2^2+2^3)(1+3)(1+5)=15\cdot4\cdot6=360.$$

For proper factors, subtract $n$ from this sum. This may or may not be faster, depending on the number and how you'd get the prime factorization, but this is the typical technique for high school contest problems of this sort.

  • $\begingroup$ @Issac: Thank you! In fact, I thought of prime factorization, but the algorithm for factorization is not fast too. $\endgroup$
    – roxrook
    Feb 18, 2011 at 23:10
  • 1
    $\begingroup$ The sum of divisors can also be written using $\sum_{i=0}^{a_k}p_k^i = (p_k^{a_k + 1})/(p_k - 1)$ for the individual factors, as may be seen from the PlanetMath article: planetmath.org/encyclopedia/FormulaForSumOfDivisors.html $\endgroup$
    – hardmath
    Feb 18, 2011 at 23:18
  • 10
    $\begingroup$ @hardmath: Absolutely—each sum is the sum of a geometric series (though I think it should probably be $$\prod_k\left(\sum_{i=0}^{a_k}p_k^i\right)=\prod_k\frac{p_k^{a_k + 1}-1}{p_k - 1}$$ (add $-1$ in the numerator). $\endgroup$
    – Isaac
    Feb 18, 2011 at 23:41
  • 3
    $\begingroup$ can anyone explain why this works? $\endgroup$ May 31, 2016 at 11:42
  • 1
    $\begingroup$ @aksam: Take the example of 120, as in the answer. A positive integer factor is the product of 0, 1, 2, or 3 factors of 2, 0 or 1 factor of 3, and 0 or 1 factor of 5. Expanding $(1+2+2^2+2^3)(1+3)(1+5)$ gives the sum of all possible such products. $\endgroup$
    – Isaac
    May 31, 2016 at 18:42

Just because it is interesting:

There is actually a (less known) recursive formula for calculating $\sigma(n)$, the sum of the divisors of $n$.

$$\sigma(n) = \sigma(n-1) + \sigma(n-2) - \sigma(n-5) - \sigma(n-7) + \sigma(n-12) +\sigma(n-15) + ..$$ Here $1,2,5,7,...$ is the sequence of generalized pentagonal numbers $\frac{3n^2-n}{2}$ for $n = 1,-1,2,-2,...$ and the signs are repetitions of $1,1,-1,-1$. The summation continues until you try to calculate $\sigma$ of something negative. However, if $\sigma(0)$ occurs in the summation (this happens precisely when $n$ is a generalized pentagonal number), it should be replaced by $n$ itself. In other words $$ \sigma(n) = \sum_{i\in \mathbb Z_0} (-1)^{i+1}\left( \sigma(n - \tfrac{3i^2-i}{2}) + \delta(n,\tfrac{3i^2-i}{2})n \right), $$ where we set $\sigma(i) = 0$ for $i\leq 0$ and $\delta(\cdot,\cdot)$ is the Kronecker delta.

Note that calculating $\sigma(n)$ requires $\sigma(n-1)$ already, therefore its complexity is at least $\mathcal O(n)$, which makes it kind of useless for practical purposes. Note however the lack of reference to divisibility in this formula, which makes it a bit miraculous and therefore worth mentioning.

Here's a reference to the Euler's paper from 1751.

  • $\begingroup$ Many thanks for a great information. Although I don't understand it completely now, I will go back to it when I'm ready. $\endgroup$
    – roxrook
    Feb 19, 2011 at 4:58
  • $\begingroup$ Is the formula correct? I get a negative sign for i=1 in your sum, and $\sigma(n-\frac{3 1^2 - 1}{2})$ has a positive sign in your first equation. Most likely, I made a mistake... (I tried it by hand using n=6). $\endgroup$
    – Unapiedra
    Oct 11, 2013 at 17:25
  • $\begingroup$ "it should be replaced by $n$ itself". So do that: $\delta(...) n$, also I find that it should be $(-1)^{i+1}$. Doing this gives me correct result for all my test cases. $\endgroup$
    – Unapiedra
    Oct 11, 2013 at 23:08
  • 1
    $\begingroup$ Thanks for pointing out this little gem! And it's far from useless. For certain purposes - like the SPOJ DIVSUM challenge where the sigma function needs to be computed in bulk - all lower sigma values are available via memoisation (caching), so that the computation of any one value needs nothing more than addition and table lookups. I coded it for SPOJ DIVSUM and it passed with flying colours (0.5 s for computing half a million sigmas, compared to one minute for one two-digit sigma w/o memoisation). $\endgroup$
    – DarthGizka
    Feb 20, 2016 at 0:31
  • 1
    $\begingroup$ @DarthGizka It was found that using a sieve algorithm is much faster than that approach. $\endgroup$
    – Paul Evans
    Aug 29, 2021 at 15:15

If $$n = a^p × b^q × c^r × \ldots$$ then total number of divisors $ = (p + 1)(q + 1)(r + 1)\ldots$

sum of divisors $\Large = [\frac{a^{(p+1)}-1}{(a \ – \ 1)} × \frac{b^{(q+1)}-1}{(b \ – \ 1)} × \frac{c^{(r+1)}-1}{(c \ – \ 1)}\ldots]$

for e.g. the divisors of $8064$ $$8064 = 2^7 × 3^2 × 7^1$$

total number of divisors $= (7+1)(2+1)(1+1) = 48$

sum of divisors $= [\frac{2^{(7+1)} –1]}{(2–1)} × \frac{3^{(2+1)} –1}{(3–1)} ×\frac{7^{(1+1)} –1}{(7–1)}]$

$= 255 × 7 × 8 = 26520$

P.S. Note that a divisor of an integer is also called a factor.

  • 1
    $\begingroup$ Thanks! I used this on ProjectEuler :D $\endgroup$ Mar 21, 2020 at 23:15

Here's a very simple formula:

$$\sum_{i=1}^n \; i\mathbin{\cdot}((\mathop{\text{sgn}}(n/i-\lfloor n/i\rfloor)+1)\mathbin{\text{mod}}2)$$

(for the sake of brevity, one can write $\mathop{\text{frac}}(n/i)$ instead of $n/i-\lfloor n/i\rfloor$).

This is a way to get the function $\text{sigma}(n)$, which generates OEIS's series A000203.

What you want is the function that generates A001065, whose formula is a slight modification of the one above (and with half its computational burden):

$$\sum_{i=1}^{n/2} \; i\mathbin{\cdot}((\mathop{\text{sgn}}(n/i-\lfloor n/i\rfloor)+1)\mathbin{\text{mod}}2)$$

That's it. Straight and easy.

  • $\begingroup$ I'm sorry but what does sign mean in this context? E.g. $sgn(1/3)$ is what? $\endgroup$
    – Vincent
    Apr 24, 2020 at 10:59
  • $\begingroup$ Hello @Vincent, $\mathop{\text{sgn}}(1/3)=1$. https://en.wikipedia.org/wiki/Sign_function $\endgroup$ Apr 24, 2020 at 14:44
  • $\begingroup$ But aren't all of them 1 then? I don't see any negative numbers appearing in the sum $\endgroup$
    – Vincent
    Apr 25, 2020 at 8:17
  • 1
    $\begingroup$ Hi again @Vincent, I hope this can help (the yellow part is editable). $\endgroup$ Apr 25, 2020 at 13:16
  • $\begingroup$ Hi yes, thank you, it makes sense now. I forgot that the sign is not just $1$ or $-1$ but also sometimes 0 $\endgroup$
    – Vincent
    Apr 25, 2020 at 16:00

If you want numerical values then the calculator at the site below will list all divisors of a given positive integer, the number of divisors and their sum. It also has links to calculators for other number theory functions such as Euler's totient function.



The other answers already talk about the basic formula, but there is a nice little trick if you're going into extremes:

say you have a very large exponent (that you normally wouldn't calculate by hand, but suppose even a computer struggles with it), like $2^x$ where x ~ $10^9$

You can actually reduce this to $log(n)$ operations.

For a shorter demonstration: sum of divisors of $x^7$. Normally you would calculate each value of $x^n$ and sum them. However, a faster way (not so noticeable for such a small exponent) is:

$x^0+x^1+x^2+x^3+x^4+x^5+x^6+x^7$ $=(x^0+x^1+x^2+x^3)*(1+x^4)$ $=(x^0+x^1)*(1+x^2)*(1+x^4)$

This works very nice for numbers such as 7, 15, etc. But it works for any other number too, as long as you simply add the part that you cannot include in polynomial factorization:

$x^0+x^1+...+x^{12}$ $=(x^0+x^1+x^2+x^3+x^4+x^5)*(1+x^6)+x^{12}$ $=(x^0+x^1+x^2)*(1+x^3)*(1+x^6)+x^{12}$

It's easy to write a computer program that does exactly this and it is able to sum to just about anything you can think of. $O(log(n))$ grows very slowly.

  • $\begingroup$ Sorry, missed @Sunil's answer, it's just a more mathematical explanation of mine. $\endgroup$
    – sqlnoob
    Dec 2, 2019 at 7:15

Here's a really simple formula:

$$ \sigma(x) = \sum_{n=1}^x \left| \text{sign}(x \text{ mod } n) - 1 \right| * n $$

Short explanation:

$ \text{sign}(x \text{ mod } n) $ evaluates to $0$ if $n$ is a divisor of $x$ (or evaluates to $1$ if $n$ isn't a divisor of $x$), so we have to negate it by subtracting one from it ($0$ -> $-1$; $1$ -> $0$) and taking the absolute value of the result. We now have either $0$ or $1$ (depending on the divisibility), which can be multiplied by $n$ to get $0$ or $n$.


The typical brute foce approach in, say, C language:

 public int divisorSum(int n){
    int sum=0;
    for(int i=1; i<= n; i++){
        if(n % i == 0){
            sum +=i;
    return sum;
  • 6
    $\begingroup$ It is a stack exchange for mathematics not for c-programming.So please write it in terms of mathematics language. $\endgroup$
    – Ripan Saha
    Jun 27, 2015 at 14:24
  • 2
    $\begingroup$ Also, this method was already proposed by the OP. $\endgroup$
    – wythagoras
    Jun 27, 2015 at 14:32
  • $\begingroup$ Not to mention that it's not even proper C. The use of public makes it look like Java. $\endgroup$ Sep 23, 2020 at 1:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .