代码解析：阅读程序-3

 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

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2022-05-31 10:48:13
 * 最后修改: 2025-09-10 12:01:29
 * 文件描述: 这是一个C++文件
****************************************************************/
/**************************************************************** 
 * Description: 
 * Author: Alex Li
 * Date: 2022-05-31 10:48:13
 * LastEditTime: 2023-09-01 19:06:27
****************************************************************/
#include <stdio.h>

#define n 100000
#define N n + 1

int m;
int a[N], b[N], c[N], d[N];
//b数组存所有的质数
//a[i]数组标记i是否为质数，1为不是质数，0为质数
//c[i]存储最小质因子的个数
//d[]存储不含最小质因子的因数和
int f[n], g[N];
//f[]存储约数的个数
//g[]存储约数和

void init()
{
    f[1] = g[1] = 1;//1的约数个数是1，约数和也是1
    //主循环：i从2到n, 线性筛
    for (int i = 2; i <= n; i++) {
        if (!a[i]) { //如果a[i]是质数，
            b[m++] = i;  
            c[i] = 1, f[i] = 2;
            d[i] = 1, g[i] = i + 1;
        }
        //用当前的素数表b[j]去线性更新i*b[j]
        for (int j = 0; j < m && b[j] * i <= n; j++) {
            int k = b[j];
            a[i * k] = 1;  
            if (i % k == 0) {
                c[i * k] = c[i] + 1;
                f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
                d[i * k] = d[i];//把最小质因子(k)的幂剥掉后剩余部分的约数和
                g[i * k] = g[i] * k + d[i];
               // 第一次出现 i % b[j] == 0 的 b[j] 就是 i 的最小质因子；代码在这条分支后立即 break，
               // 保证每个合数只经由它的最小质因子路径被“生成”一次，这正是线性筛 O(n) 的关键。
                break;
            }
            //若k不是i的因子，此时i*k的最小质因子就是k（因为线性筛按素数递增枚举）
            else {
                c[i * k] = 1;  // 新最小质因子 p 的指数从 1 开始
                f[i * k] = 2 * f[i];//约数个数翻倍,因为 i 的每一个约数，到了 x=i*k 这里都会“分裂成两种
                d[i * k] = g[i];//对 x=i*k 来说，最小质因子就是 k，而且只出现一次；把这一个 k 去掉以后，剩下的就是原来的 i。
                                //所以“剩下那一块的约数和”直接等于 i 的约数和，也就是 g[i]，于是抄过去。
                g[i * k] = g[i] * (k + 1);
               /* 新数 x 的所有约数，可以分成两拨：第一拨：i 的那些约数（原封不动）；
                第二拨：把刚才那一拨每个都再乘一个 k（因为现在多了这个新素数 k）。
                所以“约数和”就等于“原来的和”再加上“原来的和乘以 k”。用话说就是：“旧和 + 旧和 × k”。*/
            }
        }
    }
}

int main()
{
    init();

    int x;
    scanf("%d", &x);
    printf("%d %d", f[x], g[x]);
    return 0;
}