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