Sum of Divisor (Algo + Code) Part - 1

What is the divisor of a number N?

Any number k that divides N completely and leaves 0 as the remainder is a divisor of N

Example:
Divisor of 10 = 1, 2, 5, 10
Divisor of 74 = 1, 2, 37, 74

Sum of the divisor

Let \( \sigma{(n)} \) denotes the sum of the divisor of N.

\( \sigma{(10)} \) = 1 + 2 + 5 + 10 = 18

\( \sigma{(74)} \) = 1 + 2 + 37 + 74 = 114

How to find the \( \sigma{(n)} \)

Naive solution:

• Loop i through 1 to n
  
• check if i divides n,
  
• if yes, then sum such i's
  

int sumOfDivisor(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        if(n % i == 0) sum = sum + i;
    }
    return sum;
}

The time complexity of the above code is O(n).

Can we optimize this code: The answer is yes.

If n has a factor k, then another factor will be \( \frac{n}{k} \).
It is easy to see that if one factor is less than \( \sqrt[]{n} \), then another factor will be greater than \( \sqrt[]{n} \) (Think, why !!)

Also, take extra care if N is a perfect square, \( \sqrt[]{n} \) is also its factor, don't double count it

int sumOfDivisor(int n){
    int sum = 0;
    int k = sqrt(n);
    if(k * k == n) sum += k;
    for(int i = 1; i < k; i++){
        if(n % i == 0) sum = sum + i + (n / i);
    }
    return sum;
}

The time complexity of the above code is O(\( \sqrt[]{n} \)).

Can we optimize the above code further: The answer is yes.

The first observation is that if N is an odd number then its factor can't be any even number. So, we can increment by 2.

Part - 2 is coming soon

Like and Follow Me on Twitter