题解 | #质数统计#

这是一个非常经典的算法题目，结合了素数筛法与前缀和的思想。

1. 算法核心思想

如果针对每次询问 都去遍历区间内的每一个数并判断是否为质数，时间复杂度会非常高，无法通过所有测试用例。 核心思路可以分为两步：

1. 预处理质数：由于 的最大值是 ，我们可以先预处理出 到 范围内所有的数是否为质数。
2. 前缀和优化查询：为了在 的时间内回答区间计数问题，我们可以构建一个“质数个数前缀和”数组。

2. 算法具体步骤

第一步：初始化与定义

• 设定最大范围 （为了防止越界，通常设为 ）。
• 创建一个布尔数组（或标记数组） isPrime，用于记录某个数是否为质数。初始化时假设所有数都是质数（除了 0 和 1）。
• 创建一个整数数组 primeCount，用于存储前缀和。primeCount[i] 表示从整数 到 之间一共有多少个质数。

第二步：素数筛选（预处理）

使用 埃拉托斯特尼筛法（Sieve of Eratosthenes） 或 欧拉筛（线性筛）。考虑到 的数据量，埃氏筛已经足够快。

1. 将 isPrime[0] 和 isPrime[1] 标记为 false（非质数）。
2. 从 开始遍历到 ：
   • 如果 isPrime[i] 为 true，则将 的所有倍数（ 或从 开始优化）标记为 false。
3. 遍历完成后，isPrime 数组中为 true 的下标即为质数。

第三步：构建前缀和数组（预处理）

遍历 从 到 ：

• 如果 是质数（即 isPrime[i] 为 true）：
  • primeCount[i] = primeCount[i-1] + 1
• 如果 不是质数：
  • primeCount[i] = primeCount[i-1]
• 特别地，primeCount[0] = 0。

这样，primeCount[x] 就代表了区间 中质数的总数量。

第四步：处理询问

对于每一个输入的查询区间 ：

• 区间内的质数数量 = 的质数数量 - 的质数数量。
• 即输出：primeCount[r] - primeCount[l-1]。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr static int MAX = 1e6 + 5;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<bool> isPrime(MAX, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= sqrt(MAX); i++) {
        if (isPrime[i]) {
            for (int j = i * 2; j < MAX; j += i)
                isPrime[j] = false;
        }
    }

    vector<int> prefix(MAX, 0);
    for (int i = 1; i < MAX; i++) {
        if (isPrime[i])
            prefix[i] = prefix[i - 1] + 1;
        else
            prefix[i] = prefix[i - 1];
    }

    int n;
    cin >> n;
    while (n--) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << endl;
    }
}

3. 复杂度分析

假设最大数值范围为 ，询问次数为 。

时间复杂度

1. 预处理筛法：
   • 如果使用埃氏筛，复杂度为 。
   • 如果使用欧拉筛（线性筛），复杂度为 。
   • 在 的情况下，两者差异极小，计算量都在百万级别，耗时极短（毫秒级）。
2. 构建前缀和：需要遍历一次数组，复杂度为 。
3. 查询处理：每次查询只需要做一次减法运算，复杂度为 。 次查询的总复杂度为 。

• 总时间复杂度：。
  • 代入数据： 次操作。这在通常的时间限制（1秒，约 次操作）内是非常宽裕的。

空间复杂度

我们需要两个主要数组：

1. isPrime 标记数组：长度为 ，空间复杂度 。
2. primeCount 前缀和数组：长度为 ，空间复杂度 。

• 总空间复杂度：。
  • 个整数大约占用 4MB 内存，远低于通常的内存限制（如 256MB）。