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?
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;
}