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 $7\times 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\times3^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