Learning C++ Programming from Scratch, Day 408: 1084 – Sum of Proper Divisors; Problem Set Answers; Fourth 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.

• 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 checking 5 exceeds √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::
int main() {    int n, i, s = 0; // Define variables: n stores the input number, i is the loop variable, s stores the sum of divisors (initially 0)
    cin >> n; // Read an integer from user input
    // Iterate from 2 to the square root of n (mathematical optimization)    for(i = 2; i <= sqrt(n); i++)     {        // Check if i is a divisor of n (can it divide evenly?)        if(n % i == 0)         {            // Check if i is the square root of n (like 5 for 25)            if(i == sqrt(n))             {                s = s + i; // If it is the square root, add it only once            }            else             {                // For normal divisors, add both i and the corresponding divisor n/i (like 2 and 10 for 20)                s = s + i + n / i;            }        }    }
    cout << s; // Output the calculated sum of divisors
    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 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

① Variable Definition

• <span>n</span>: stores the number input by the user.

• <span>i</span>: loop variable, starts checking from 2.

• <span>s</span>: accumulator, records the current value of the sum of divisors (initially 0).

② Main Process

1. <span>cin >> n</span>: reads user input.

2. <span>for loop</span>: iterates from 2 to √n (mathematical optimization).

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

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

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

<span>cout << s</span>: outputs the final 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 → s=12.

i=3:

• 20%3≠0 → Skip.

i=4:

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

i=5 > √20 → Loop ends.

Output 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 perfect square (like 25 = 5 × 5).

Square Root Optimization:

• Checking up to √n allows finding all divisors.

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

5. Precautions

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.

• Use i*i <= n to 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 running process of small numbers with paper and pen.

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

3. Think: Why do we only need 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.