POTD 21 October: Sum of all divisors from 1 to n
Given a positive integer N., The task is to find the value of Σi from 1 to N F(i) where function F(i) for the number i is defined as the sum of all divisors of i.
Example:
Input: 4
Output: 15
Explanation:
F(1) = 1
F(2) = 1 + 2 = 3
F(3) = 1 + 3 = 4
F(4) = 1 + 2 + 4 = 7
ans = F(1) + F(2) + F(3) + F(4)
= 1 + 3 + 4 + 7
= 15
Input: 5
Output: 21
Sum of all divisors from 1 to n using basic mathematical concept:
The basic idea is to calculate the sum of divisors for a given number N by iterating through numbers from 1 to N and accumulating the contributions of each divisor to the total sum. For each number ‘i’ in the range, it calculates how many times ‘i’ divides ‘N’ without a remainder and adds this contribution to the sum. The final sum represents the sum of divisors for the input N.
Step-by-step approach:
- A long long variable called “sum” is initialized to zero. This variable will be used to accumulate the sum of divisors.
- A for loop iterates from 1 to N. This loop is used to find the divisors of the input number N.
- Inside the loop, the program calculates the contribution of each divisor to the sum. For each value of ‘i’ in the loop, it calculates (N / i) * i. Here’s how this works:
- N / i gives the number of times ‘i’ divides ‘N‘ without a remainder. It essentially represents how many times ‘i’ appears as a divisor in ‘N‘.
- Multiplying (N / i) by ‘i’ essentially gives the total value contributed by the divisor ‘i’ to the sum of divisors.
- The result of (N / i) * i is added to the “sum” variable, effectively accumulating the sum of divisors.
- Once the loop finishes iterating from 1 to N, the method returns the final value of the “sum,” which represents the sum of divisors of the input number N.
Below is the implementation of the above approach:
C++
class Solution {
public:
long long sumOfDivisors(int N)
{
long long sum = 0;
for (int i = 1; i <= N; ++i)
sum += (N / i) * i;
return sum;
}
};
|
