解析：阅读程序-2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/**************************************************************** 
 * Description: 2023CSP_S_R2
 * Author: Alex Li
 * Date: 2024-06-04 09:31:04
 * LastEditTime: 2024-09-12 22:46:55
****************************************************************/
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

long long solve1(int n) {
    vector<bool> p(n + 1, true);  //判断是否为素数，true为素数
    vector<long long> f(n + 1, 0), g(n + 1, 0);
    f[1] = 1;
    //埃氏筛法找素数  
    for (int i = 2; i * i <= n; i++) {
        if (p[i]) {
            vector<int> d;
            //在d里存i的幂次，如果i=2  d中就是2，4，8... 
            for (int k = i; k <= n; k *= i)d.push_back(k); 
            //把d中的数反转
            reverse(d.begin(), d.end());
            for (int k : d) { //遍历向量 d 中的每个元素 k
                for (int j = k; j <= n; j += k) {// 从 k 开始，步长为 k，遍历 j
                    if (p[j]) {// 如果 p[j] 为 true
                        p[j] = false; // 将 p[j] 设为 false，表示 j 不是素数
                        f[j] = i; //j的最小质因子i
                        g[j] = k; //最小质因子的最大幂次
                    }
                    
                }
               
            }
        }
    }
    //大于sqrt(n)的部分，如果是i质数，把相应的f和g数组填满
    for (int i = sqrt(n) + 1; i <= n; i++) {
        if (p[i]) {
            f[i] = i;
            g[i] = i;
        }
    }
    long long sum = 1; // 初始化总和为1（即f[1]）
    /*
    sum求所有数字i的约数和f[i]的和, 
    比如2的约数有1，2，之和是3，4的约数有1，2，4，约数和是7
    从2~10的约数和分别是3 4 7 6 12 8 15 13 18
    sum=1+f[2]+...f[n]=87
    */
    for (int i = 2; i <= n; i++) {
        f[i] = f[i / g[i]] * (g[i] * f[i] - 1) / (f[i] - 1);
        sum += f[i];
    }
    return sum;
}
// 直接枚举法计算每个数的约数之和
long long solve2(int n) {
    long long sum = 0;
    // 对于每个数i，累加i的所有倍数
    for (int i = 1; i <= n; i++) {
        sum += i * (n / i);// i是n/i个数的约数
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    cout << solve1(n) << endl;
    cout << solve2(n) << endl;
    return 0;
}