Sum of All Divisors from 1 to N

Introduction

In this blog, we will discuss the problem of finding the sum of all divisors from 1 to N. This problem is an observation-based problem with a tint of simple mathematics. We will explore different approaches and algorithms to solve this problem efficiently.

Understanding the Problem

The problem statement is self-explanatory. Given a number N, we need to find the sum of all its divisors from 1 to N.

Brute Force Approach

Initially, we can think of solving this problem using a brute force approach. We can iterate from 1 to N and check if each number is a divisor of N. If it is a divisor, we add it to the sum. However, this approach is not optimal for large values of N.

Optimized Approach

To optimize the solution, we can use a contribution technique. Instead of finding all the divisors individually, we can find the contribution of each number in the sum. Let's understand this technique with an example:

For N = 8:

• 1 can contribute to all numbers from 1 to 8
• 2 can contribute to all even numbers from 2 to 8
• 3 can contribute to 3, 6
• 4 can contribute to 4
• 5 can contribute to 5
• 6 can contribute to 6
• 7 can contribute to 7
• 8 can contribute to 8

Using this contribution technique, we can calculate the sum of all divisors without finding them individually.

Implementation

Let's implement the optimized approach in code:

long long sumOfDivisors(int N) {
    long long sum = 0;
    for (int i = 1; i <= N; i++) {
        sum += (N / i) * i;
    }
    return sum;
}

The time complexity of this solution is O(N), and the space complexity is O(1) as we are using only a few variables.

Conclusion

In this blog, we discussed the problem of finding the sum of all divisors from 1 to N. We explored the brute force approach and an optimized approach using the contribution technique. The optimized approach is more efficient for large values of N. We implemented the optimized approach in code with a time complexity of O(N) and a space complexity of O(1).

Thank you for reading and have a nice day!