Confusion with sum-of-divisors algorithm (code)

Hey guys. I have recently stumbled upon somebody else's code which used a function for calculating sum of divisors of a certain number. The function is pretty fast and returns correct output.
(example: for 12, divisors are 1, 2, 3, 4, 6 and 12, so sum = 28)

However, while I can read the code without a problem, I can't understand how this algorithm works.
Can somebody more experienced than me explain the theory behind this code?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int sum_of_divisors(int n)
{
	int sum = 1;

	for(int k = 2; k * k <= n; ++k)
	{
		int p = 1;
		while(n % k == 0)
		{
			p = p * k + 1;
			n /= k;	
		}

		sum *= p;
	}

	if(n > 1)
		sum *= 1 + n;

	return sum;
}


Thanks in advance.
Last edited on
That is a neat piece of math here. Really elegant. Sadly I am bad at explaining, so I tried to find explanation online. Here are two examples:
http://mathschallenge.net/library/number/sum_of_divisors
http://math.stackexchange.com/questions/22721/is-there-a-formula-to-calculate-the-sum-of-all-proper-divisors-of-a-number
Well, the method indeed is hard to explain.

But I get it now. Thanks man :)
Topic archived. No new replies allowed.