以下摘要由GPT-4o生成:
题目要求计算正整数 N 的每个数的最小质因子的总和，即求和 $\sum\limits_{i=2}^N F(i)$。输入中包含多个测试数据，数量 T 可达 10^6，而 N 的范围为 2 到 2×10^7。为了高效解决问题，可以采用线性筛法（或欧拉筛），其相较于传统的试除法具有更好的性能表现，能够在较短时间内完成质因子的计算并输出结果。

题目链接[15.最小质因子之和(Hard Version) - 蓝桥云课]

题目描述

定义 F(i) 表示整数 i 的最小质因子。现给定一个正整数 N，请你求出 $\sum\limits_{i=2}^N F(i)$

输入描述

第 11 行为一个整数 T，表示测试数据数量。

接下来的 T 行每行包含一个正整数* N*。

$1≤T≤10^6，2≤N≤2×10^7。$

输出描述

输出共 T 行，每行包含一个整数，表示答案。

输入输出样例

示例 1

输入

1
2
3
4
3
5
10
15

输出

1
2
3
12
28
59

普通素数的求法(试除法)

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
#include <iostream>
#include <cmath>
using namespace std;

const int max_n = 2e7;
int minp[max_n + 1];
long long sum[max_n + 1];

void precompute() {
    for (int i = 2; i <= max_n; ++i) {
        bool is_prime = true;
        for (int j = 2; j <= sqrt(i); ++j) {
            if (i % j == 0) {
                minp[i] = j; //合数的质因数为j
                is_prime = false;
                break;//保证找到最小质因数
            }
        }
        if (is_prime) minp[i] = i;
    }
}

int main() {
    // 预处理（实际会超时）
    precompute();
    
    // 计算前缀和
    for (int i = 2; i <= max_n; ++i) {
        sum[i] = sum[i-1] + minp[i];
    }
    
    // 处理查询
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        cout << sum[N] << endl;
    }
    return 0;
}

线性筛质数（欧拉筛）

前置知识：[算术基本定理_百度百科]

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
#include <iostream>
using namespace std;

const int max_n = 2e7;
int minp[max_n + 1];      // 最小质因子表
long long sum[min_n + 1]; // 前缀和数组
bool st[max_n + 1];       // 筛标记
int primes[max_n];        // 质数表
int cnt;

// 线性筛法预处理最小质因子
void get_minp() {
    for (int i = 2; i <= max_n; i++) {
        if (!st[i]) { // i 是质数
            primes[cnt++] = i;
            minp[i] = i; // 质数的最小质因子是自身
        }
        // 用 i 的最小质因子筛掉合数
        for (int j = 0; j < cnt && primes[j] * i <= max_n; j++) {
            int t = primes[j] * i;//算数基本定理，一个合数可以被分解为多个质数的乘积;
            st[t] = true;
            minp[t] = primes[j]; // 合数 t 的最小质因子是 primes[j]
            if (i % primes[j] == 0) break; // 避免重复筛
        }
    }
}

int main() {
    // 预处理最小质因子和前缀和
    get_minp();
    sum[0] = sum[1] = 0;
    for (int i = 2; i <= max_n; i++) {
        sum[i] = sum[i-1] + minp[i];
    }

    // 处理输入输出
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        cout << sum[N] << endl;
    }
    return 0;
}

对比：线性筛法的优势

方法 预处理时间 查询时间 适用规模
试除法 O(N *sqrt( N)) O(1) N ≤ 10^4
线性筛法 O(N) O(1) N ≤ 2×10^7