Sum of Divisors of an Integer
Problem
Given an integer N, find the sum of all its divisors.
For example, find Sum Of Divisors (SOD) of $12$. $12$ has the following divisors, ${1, 2, 3, 4, 6, 12}$. So $SOD (12 ) = 1 + 2 + 3 + 4 + 6 + 12 = 28$.
Sum of Divisor Function: $SOD(N)$ or $\sigma_{1}(N)$
The Sum of Divisors of $N$ is also called $\sigma_{1}(N)$. That’s just a fancy way of saying Sum of Divisors of $N$. You can read more on it from Wiki. I will refer to Sum of Divisors of $N$ as either $\sigma_{1}(N)$ or $SOD(N)$. They both mean same.
Inefficient Solutions
Let us first look into some simple, but inefficient, solutions. These solutions are similar to the naive solutions we came up for “Number of Divisors of an Integer“.
Loop Till $N$
This is the simplest solution. We loop from $1 \to N$ and add all numbers that divide $N$.
Loop Till $\sqrt{N}$
If $N = A \times B$, where $A \leq B$, $A$ must be $\leq \sqrt{N}$. Using this fact we can run a loop from $1 \to \sqrt{N}$ and add all numbers that divide $N$ and their complements to result.
int SOD ( int n ) { int sqrtn = sqrt ( n ); int res = 0; for ( int i = 1; i < sqrtn; i++ ) { if ( n % i == 0 ) { res += i; //"i" is a divisor res += n / i; //"n/i" is also a divisor } } if ( n % sqrtn == 0 ) { if ( sqrtn * sqrtn == n ) res += sqrtn; //Perfect Square. else { res += sqrtn; //Two different divisor res += n / sqrtn; } } return res; }
At line $10$, we handle $sqrtn$ separately cause when $N$ is a perfect square we don't get different values for ${A, B}$ pair. For example, for $49$ we have a divisor pair $7times 7$. We need to add $7$ only once in our result.
Using Prime Factorization
It is possible to find $SOD(N)$ using the prime factorization of $N$. Let us see an example for it.
$Let \ N = 12,$
$SOD(12)= 1 + 2 + 3 + 4 + 6 + 12,$
$SOD(12) = (2^0 \times 3^0) + (2 ^1 \times 3^0) + (2^0 \times 3^1) + (2^2 \times 3^0) + (2^1 \times 3^1) + (2^2 \times 3^1),$
$SOD(12) = 2^0 ( 3^0 + 3^1 ) + 2^1 ( 3^0 + 3^1 ) + 2^2 ( 3^0 + 3^1 ),$
$SOD(12) = ( 2^0 + 2^1 + 2^2 ) \times ( 3^0 + 3^1)$
This pattern emerges with any value of N. More generally, if $N= p_1^{a_1} \times p_2^{a_2} \times ... p_k^{a_k}$, then $$ SOD(N) = (p_1^0 + p_1^1 + p_1^2 ... p_1^{a_1} ) \times (p_2^0 + p_2^1 + p_2^2 ... p_2^{a_2} ) \times ... (p_k^0 + p_k^1 + p_k^2 ... p_k^{a_k} ) $$Using this formula and our code for Prime Factorization, we can write the function $SOD(N)$. This code is similar to $factorize()$. We only need to modify it in few places.
int SOD( int n ) { int res = 1; int sqrtn = sqrt ( n ); for ( int i = 0; i < prime.size() && prime[i] <= sqrtn; i++ ) { if ( n % prime[i] == 0 ) { int tempSum = 1; // Contains value of (p^0+p^1+...p^a) int p = 1; while ( n % prime[i] == 0 ) { n /= prime[i]; p *= prime[i]; tempSum += p; } sqrtn = sqrt ( n ); res *= tempSum; } } if ( n != 1 ) { res *= ( n + 1 ); // Need to multiply (p^0+p^1) } return res; }
For each prime we find in factorization, we need to find the corresponding value of $(p^0+p^1+...p^a)$. For that, we use tempSum
in line $6$. It contains $p^0$ initially. Then for each successful division at line $8$, we increase the power of $p$ in line $10$ and add it to tempSum
in line $11$. Eventually, we multiply the final sum to result at line $14$.
In line $17$, we check if we are left with a sole prime remainder. In this case, we know that $n$ is a prime so we simply multiply $p^0 + p^1 = 1 + n$ to the result.
Reference
- Wiki - Divisor Function - https://en.wikipedia.org/wiki/Divisor_function
- forthright48 - Number of Divisors of an Integer - https://forthright48.com/2015/07/number-of-divisors-of-integer.html
- forthright48 - Prime Factorization - https://forthright48.com/2015/07/prime-factorization-of-integer.html