# Finding the SUM OF DIVISORS of a number

By | September 5, 2015

# Finding the SUM OF DIVISORS of a number. Divisor Summation. Sum of Factors of a Number

### Problem:

Given a number N, we need to print the Sum of Divisors (Proper and Improper).

Example :

Input : 20
Ans:
Improper Summation : 42
Proper Summation: 22

Solution:

Here, the main point that need to be understood is that divisors always occurs in pairs.

1. If DIV is a divisor of N/DIV is also a divisor.
2. The smaller of the pair would always be <= Sqrt(N).

Algotrithm:

1. Initialise Sum=0.
2. for each i (1<=i< sqrt(N)) if N%i==0, add i and N/i to sum
3. After the above loop, if ( i*i==N) ,then add i
4. For improper divisors you have the answer.
5. For proper divisors, subtract N from Sum.

The step 3 of the above algorithm, helps us to add sqrt(N) as a divisor only once, hence we keep it out of the loop.

Here is the working code:

```#include <bits/stdc++.h>
using namespace std;
#define LL long long

void DivisorSummation(int N)
{
LL sum=0;
int i;
for(i=1; (i*i) < N; ++i)
if(N%i==0)
sum+= i + N/i;
if( i*i == N)
sum+=i;
/*we have sum of improper divisors till now*/
cout<<"Improper Divisor sum: "<<sum<<endl;

sum-=N; //for proper divisors
cout<<"Proper Divisor sum: "<<sum<<endl;

}

int main() {
DivisorSummation(10);
DivisorSummation(20);
return 0;
}```

Output:

```Improper Divisor sum: 18
Proper Divisor sum: 8
Improper Divisor sum: 42
Proper Divisor sum: 22
```