题解 | #质数统计#

题目链接

质数统计

题目描述

给定 $Q$ 次询问，每次询问一个闭区间 $[l, r]$ ，请你输出该区间内质数（素数）的数量。

解题思路

本题要求对多个区间进行质数数量的统计。如果对每个查询都遍历区间 $[l, r]$ 并逐个判断数字是否为质数，当区间很大或查询次数很多时，效率会非常低下，导致超时。

这是一个典型的可以使用预处理和前缀和思想解决的区间查询问题。

预处理质数

首先，我们需要一个高效的方法来判断在一个较大范围内哪些数是质数。埃拉托斯特尼筛法（埃氏筛）是完成这项任务的理想选择。我们可以创建一个布尔数组 $is\_prime$ ，预先筛出从 $1$ 到数据上限（例如 $10^6$ ）的所有质数。
构建前缀和数组

为了能够快速查询任意区间 $[l, r]$ 内的质数数量，我们可以构建一个前缀和数组。我们定义一个数组 $prefix\_sum$ ，其中 $prefix\_sum[i]$ 存储区间 $[1, i]$ 内质数的总数量。

这个数组可以基于埃氏筛的结果 $is\_prime$ 数组来计算：
- $prefix\_sum[0] = 0$
- 对于 $i > 0$ ，递推公式为： $prefix\_sum[i] = prefix\_sum[i-1] + (is\_prime[i] ? 1 : 0)$
响应查询

在完成了预处理之后，对于任何一个查询区间 $[l, r]$ ，其内部的质数数量可以通过前缀和数组在 $\mathcal{O}(1)$ 的时间内计算出来。

其计算公式为： $prefix\_sum[r] - prefix\_sum[l-1]$ 。

这个公式的含义是：用 $[1, r]$ 区间内的质数总数减去 $[1, l-1]$ 区间内的质数总数，剩下的就是区间 $[l, r]$ 内的质数总数。

综上，我们首先进行一次性的筛法和前缀和计算，然后就可以快速回答所有查询了。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

const int MAX_R = 1000001;
vector<bool> is_prime(MAX_R, true);
vector<int> prefix_sum(MAX_R, 0);

void sieve_and_prefix_sum() {
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p < MAX_R; ++p) {
        if (is_prime[p]) {
            for (int i = p * p; i < MAX_R; i += p) {
                is_prime[i] = false;
            }
        }
    }

    for (int i = 1; i < MAX_R; ++i) {
        prefix_sum[i] = prefix_sum[i - 1];
        if (is_prime[i]) {
            prefix_sum[i]++;
        }
    }
}

int main() {
    sieve_and_prefix_sum();
    
    int Q;
    cin >> Q;
    while (Q--) {
        int l, r;
        cin >> l >> r;
        cout << prefix_sum[r] - prefix_sum[l - 1] << endl;
    }
    
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static final int MAX_R = 1000001;
    static boolean[] is_prime = new boolean[MAX_R];
    static int[] prefix_sum = new int[MAX_R];

    static {
        Arrays.fill(is_prime, true);
        is_prime[0] = is_prime[1] = false;
        for (int p = 2; p * p < MAX_R; p++) {
            if (is_prime[p]) {
                for (int i = p * p; i < MAX_R; i += p) {
                    is_prime[i] = false;
                }
            }
        }

        prefix_sum[0] = 0;
        for (int i = 1; i < MAX_R; i++) {
            prefix_sum[i] = prefix_sum[i - 1];
            if (is_prime[i]) {
                prefix_sum[i]++;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int Q = sc.nextInt();
        while (Q-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(prefix_sum[r] - prefix_sum[l - 1]);
        }
    }
}

MAX_R = 1000001
is_prime = [True] * MAX_R
prefix_sum = [0] * MAX_R

def sieve_and_prefix_sum():
    global is_prime, prefix_sum
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(MAX_R**0.5) + 1):
        if is_prime[p]:
            for i in range(p * p, MAX_R, p):
                is_prime[i] = False
    
    for i in range(1, MAX_R):
        prefix_sum[i] = prefix_sum[i - 1]
        if is_prime[i]:
            prefix_sum[i] += 1

def main():
    sieve_and_prefix_sum()
    Q = int(input())
    for _ in range(Q):
        l, r = map(int, input().split())
        print(prefix_sum[r] - prefix_sum[l - 1])

if __name__ == "__main__":
    main()

算法及复杂度

算法：数论、埃拉托斯特尼筛法、前缀和
时间复杂度：预处理阶段，埃氏筛法的时间复杂度为 $\mathcal{O}(M \cdot \log \log M)$ ，计算前缀和的复杂度为 $\mathcal{O}(M)$ ，其中 $M$ 是区间的最大右端点。处理 $Q$ 次查询的总时间复杂度为 $\mathcal{O}(M \cdot \log \log M + Q)$ 。
空间复杂度：需要一个布尔数组和一个整数数组来存储质数信息和前缀和，空间复杂度为 $\mathcal{O}(M)$ 。