GESP C++ 五级质数统计实战：前缀和与欧拉筛求解洛谷P1865题解

本题是一道典型的数论与预处理优化结合的题目，考察质数筛选与快速区间查询，适合GESP C++四级及以上水平或对算法与数据结构感兴趣的学习者练习。

题目要求

题目描述

给定区间，求区间内质数的个数。

输入格式

第一行有两个整数 n, m，分别代表询问次数 n 和给定区间的右端点最大值 m。
接下来 n 行，每行两个整数 l, r，代表一次查询。

输出格式

对于每次查询输出一行，若 l, r 均在 [1, m] 范围内，则输出区间 [l, r] 内质数的个数，否则输出 Crossing the line。

输入输出样例 #1

输入 #1

2 5
1 3
2 6

输出 #1

2
Crossing the line

数据范围与约定

• 对于 100% 的数据，保证 1 ≤ n ≤ 10^6。
• 对于 100% 的数据，保证 1 ≤ l ≤ r ≤ 10^6，1 ≤ m ≤ 10^6。

题目分析

这道题要求我们在 n 次询问中，快速计算给定区间 [l, r] 内质数的个数。核心挑战在于数据规模大（n 和 m 均可达到 10^6），必须采用高效的预处理和查询方法。

1. 朴素算法的局限性
如果对每次询问都遍历区间并判断每个数是否为质数（试除法），单次时间复杂度约为 O(√r)，总复杂度会达到 O(n * m)，对于 10^6 的数据量必然超时（TLE）。

2. 高效的预处理：线性筛（欧拉筛）
由于所有询问的区间右端点 r 都不超过 m，我们可以预先计算出 1 到 m 之间的所有质数。线性筛（欧拉筛）算法是此场景下的最佳选择，它可以在 O(m) 的线性时间复杂度内完成筛选。
其核心思想是确保每个合数只被它的最小质因子筛掉一次。这不仅保证了效率，也是理解数论和编程语言（如C++）实现细节的绝佳实践。

3. 查询优化：前缀和思想
预处理出质数表后，若每次查询仍遍历 [l, r] 统计，单次复杂度为 O(r-l)，最坏情况下总复杂度仍可能过高。为了达到 O(1) 的查询速度，需要引入前缀和技巧。

• 定义前缀和数组 pre[i]，表示区间 [1, i] 内质数的总个数。
• 递推公式：pre[i] = pre[i-1] + (is_prime[i] ? 1 : 0)。
• 对于任意查询 [l, r]，其答案即为 pre[r] - pre[l-1]。

4. 边界处理
题目要求查询区间必须落在 [1, m] 内，否则输出 “Crossing the line”。在回答询问前，需先判断 r > m 或 l < 1。

算法流程总结

1. 读取 n 和 m。
2. 使用线性筛预处理出 1 到 m 的质数标记数组。
3. 基于质数标记数组计算前缀和数组。
4. 依次处理 n 次询问，利用前缀和公式 O(1) 输出答案或判断越界。
   整体时间复杂度为 O(m + n)，能够高效处理大规模数据。

示例代码 (C++)

以下代码完整实现了上述分析思路，包含线性筛与前缀和的应用。

#include <iostream>
#include <vector>
// 标记数组：is_prime[i] 为 1 表示 i 是质数，为 0 表示 i 是合数
int is_prime[1000005];
// 前缀和数组：pre[i] 表示 [1, i] 区间内质数的个数
int pre[1000005];

int main() {
    int n, m;
    // 输入询问次数 n 和最大范围 m
    std::cin >> n >> m;
    std::vector<int> primes;  // 用于存储筛选出的质数
    // 初始化：假设 2 到 m 之间的数都是质数
    std::fill(is_prime + 2, is_prime + m + 1, 1);
    // 线性筛（欧拉筛）算法筛选质数
    for (int i = 2; i <= m; i++) {
        if (is_prime[i] == 1) {
            primes.push_back(i);  // i 是质数，加入列表
        }
        // 遍历已有质数，标记合数
        for (int p : primes) {
            if (p * i > m) {
                break;  // 如果超出最大范围 m，停止这一轮标记
            }
            is_prime[p * i] = 0;  // 标记 p * i 为合数
            if (i % p == 0) {
                break;  // 关键：保证每个合数只被其最小质因子筛去，保证线性时间复杂度
            }
        }
    }
    // 计算质数个数的前缀和
    for (int i = 1; i <= m; i++) {
        pre[i] = pre[i - 1] + is_prime[i];
    }
    // 处理 n 次询问
    for (int i = 0; i < n; i++) {
        int l, r;
        std::cin >> l >> r;
        // 判断查询区间是否超出有效范围 [1, m]
        if (r > m || l < 1) {
            std::cout << "Crossing the line" << "\n";
            continue;
        }
        // 利用前缀和计算区间 [l, r] 内的质数个数
        std::cout << pre[r] - pre[l - 1] << "\n";
    }
    return 0;
}

本题“luogu-P1865”可在洛谷题库进行在线评测。