Learning C++ Programming from Scratch, Day 407: 1084 – Sum of Proper Divisors; Problem Set Answers; Third Method

1084 – Sum of Proper Divisors

This program solves a mathematical problem: calculating the sum of all proper divisors of a number (excluding 1 and the number itself).

How does the program work?

1. First, the user inputs a number (for example, 20).

2. The program will do the following:

• Add 4 and its corresponding 5 to the total sum.

• Skip and do not add others.

• Add 2 and its corresponding 10 to the total sum.

• Start checking from 2 (since the problem requires excluding 1).

• Check if 2 is a divisor of 20 (20 ÷ 2 = 10, divisible).

• Check if 3 is a divisor (20 ÷ 3 ≈ 6.66, not divisible).

• Check if 4 is a divisor (20 ÷ 4 = 5, divisible).

• Stop checking when exceeding √20 ≈ 4.47.

Finally, the total sum is obtained: 2 + 10 + 4 + 5 = 21.

Special Note::

• Use a loop to iterate from 2 to √n (mathematical optimization).

• When encountering a divisible number:

• If it is a square root (like 5 for 25), add it only once.

• Otherwise, add both the number and its corresponding divisor (like 2 and 10 for 20).

• Finally, return the accumulated total sum.

Reference Code

#include<bits/stdc++.h> // Include all standard library headers for simplified programming
using namespace std;    // Use the standard namespace to avoid writing std::
// Define the function to calculate the sum of divisors
int fun(int n) // n is the positive integer to calculate
{    int r = 0; // Initialize the sum to 0
    // Iterate from 2 to the square root of n (optimization key)
    for(int i = 2; i <= sqrt(n); i++)     {
        // Check if i is a divisor of n
        if(n % i == 0)         {
            // Handle the special case of square numbers (like 25 = 5 × 5)
            if(i == sqrt(n))             {
                r += i; // Add the square root only once
            }
            else // Normal divisor case            {
                r = r + i + (n / i); // Add i and its corresponding divisor
            }
        }
    }
    return r; // Return the final sum
}
// Main function
int main() {
    int n; // Store the user input number
    cin >> n; // Read input
    cout << fun(n); // Call the function and output the result
    return 0; // Program ends normally
}

1. Function of the Program

This program can calculate: given any positive integer, find the sum of all its proper divisors (excluding 1 and the number itself). For example:

• Input 20 → Divisors are 2, 4, 5, 10 → Sum is 2 + 4 + 5 + 10 = 21.

• Input 25 → Divisor is only 5 → Sum is 5.

• Input 17 → No proper divisors → Sum is 0.

2. Core Component Analysis

① fun Function

• <span>int r=0</span>: Initialize the sum.

• <span>for Loop</span>: Iterate from 2 to √n (mathematical optimization).

• <span>if(n%i==0)</span>: Check for divisors.

• Special case handling for square roots (like 25 = 5 × 5).

• Normal case: add both i and n/i.

• <span>return r</span>: Return the final result.

② Main Function

• <span>cin>>n</span>: Read user input.

• <span>cout<<fun(n)</span>: Call and output the result.

3. Key Algorithm Explanation

Mathematical Optimization Principle:

• If a is a divisor of n, then b = n/a is also a divisor.

• When a exceeds √n, b will be less than √n.

• Thus, checking only up to √n is sufficient to find all divisor pairs.

Example Process (n=20):

1. i=2:

• 20%2=0 → Not a square root → Add 2 and 10 → r=12.

i=3:

• 20%3≠0 → Skip.

i=4:

• 20%4=0 → Not a square root → Add 4 and 5 → r=21.

i=5 > √20 → Loop ends.

Return 21.

4. Important Concept Explanation

Divisor Pairs:

• Each divisor a corresponds to a divisor b = n/a.

• When a < b, we find both divisors simultaneously.

• When a = b, this is a square number (like 25 = 5 × 5).

Square Root Optimization:

• Checking up to √n allows finding all divisors.

• Greatly reduces the number of iterations (from n to √n).

5. Important Considerations

1. Boundary Cases:

• Inputting 1 should return 0 (the program handles this correctly).

• Prime numbers will return 0 (like 17).

Number Range:

• For large numbers, sqrt(n) may have precision issues.

• Using i*i<=n can avoid floating-point operations.

Optimization Suggestions:

• Pre-calculate sqrt(n) and store it in a variable.

• Use a faster square root algorithm.

6. Learning Suggestions

Beginners can:

1. Simulate the operation process of small numbers with pen and paper.

2. Try modifying the program to print each found divisor.

3. Think: Why is it sufficient to check up to √n?

4. Challenge: How to modify the program to include 1 as a divisor?

This program effectively demonstrates:

• The application of loop structures.

• The use of mathematical optimization in practical programming.

• Handling of boundary conditions.

• The concept of function encapsulation.

I hope this detailed explanation helps beginners fully understand this program! If there are any questions, it is recommended to run the program and observe its behavior.