题目链接

HIGH9 质数统计

题目描述

给定 T 个查询，每个查询包含一个闭区间 [L, R]。对于每个查询，请你计算并输出在该区间内共有多少个质数。

解题思路

这是一个典型的区间查询问题，如果对每个查询都遍历区间内的数并逐一判断是否为质数，当查询次数 T 或区间长度很大时，效率会非常低下。

解决这类问题的标准方法是预处理 + O(1)查询，具体分为两步：

  1. 使用筛法找出所有质数：

    • 和上一题类似，我们首先使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来预处理出一个范围内的所有质数。
    • 创建一个布尔数组 is_prime，大小为 N+1（N 是 R 的最大可能值），并标记出从 2 到 N 所有的质数。

  2. 构建前缀和数组：

    • 为了快速回答任意区间 [L, R] 的质数个数，我们可以再创建一个前缀和数组，我们称之为 prefix_primes。
    • prefix_primes[i] 的定义是：在 [1, i] 这个区间内质数的总数量。
    • 这个数组可以在筛法执行完毕后，通过一次线性遍历来构建：
      • prefix_primes[0] = 0
      • 从 i = 1 到 N 遍历：
        • prefix_primes[i] = prefix_primes[i-1] （继承前一个位置的计数值）
        • 如果 is_prime[i] 为 true，则 prefix_primes[i] 再加 1。

  3. 回答查询：

    • 经过以上两步预处理后，对于任何一个查询 [L, R]，区间内质数的数量就是 prefix_primes[R] - prefix_primes[L-1]。
    • 这个查询操作的时间复杂度是 ，因此可以非常迅速地处理大量查询。

代码

#include <iostream>
#include <vector>

using namespace std;

const int N_MAX = 1000001;
bool is_prime[N_MAX];
int prefix_primes[N_MAX];

void precompute() {
    // 1. 埃拉托斯特尼筛法
    fill(is_prime, is_prime + N_MAX, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p < N_MAX; ++p) {
        if (is_prime[p]) {
            for (int i = p * p; i < N_MAX; i += p) {
                is_prime[i] = false;
            }
        }
    }

    // 2. 构建前缀和数组
    prefix_primes[0] = 0;
    for (int i = 1; i < N_MAX; ++i) {
        prefix_primes[i] = prefix_primes[i - 1];
        if (is_prime[i]) {
            prefix_primes[i]++;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute();

    int t;
    cin >> t;
    while (t--) {
        int l, r;
        cin >> l >> r;
        if (l > r) swap(l,r); // 以防万一
        if (l <= 0) l = 1;
        if (r >= N_MAX) r = N_MAX - 1;
        
        cout << prefix_primes[r] - prefix_primes[l - 1] << endl;
    }
    return 0;
}

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

public class Main {
    static final int N_MAX = 1000001;
    static boolean[] isPrime = new boolean[N_MAX];
    static int[] prefixPrimes = new int[N_MAX];

    static {
        // 1. 筛法
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p < N_MAX; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i < N_MAX; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        // 2. 前缀和
        prefixPrimes[0] = 0;
        for (int i = 1; i < N_MAX; i++) {
            prefixPrimes[i] = prefixPrimes[i - 1];
            if (isPrime[i]) {
                prefixPrimes[i]++;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            
            // 确保 l <= r，并处理边界情况
            if (l > r) { int temp = l; l = r; r = temp; }
            if (l <= 0) l = 1;
            if (r >= N_MAX) r = N_MAX - 1;

            System.out.println(prefixPrimes[r] - prefixPrimes[l - 1]);
        }
    }
}

N_MAX = 1000001
is_prime = [True] * N_MAX
prefix_primes = [0] * N_MAX

# 1. 埃拉托斯特尼筛法
is_prime[0] = is_prime[1] = False
for p in range(2, int(N_MAX**0.5) + 1):
    if is_prime[p]:
        for i in range(p * p, N_MAX, p):
            is_prime[i] = False

# 2. 构建前缀和数组
for i in range(1, N_MAX):
    prefix_primes[i] = prefix_primes[i - 1]
    if is_prime[i]:
        prefix_primes[i] += 1

# 读取输入并查询
t = int(input())
for _ in range(t):
    l, r = map(int, input().split())
    
    # 确保 l <= r，并处理边界
    if l > r:
        l, r = r, l
    if l <= 0:
        l = 1
    if r >= N_MAX:
        r = N_MAX - 1

    print(prefix_primes[r] - prefix_primes[l - 1])

算法及复杂度

  • 算法：埃拉托斯特尼筛法、前缀和
  • 时间复杂度：。筛法和前缀和的预处理时间复杂度为 ，其中 N 是数据上限 (10^6)。之后的 T 次查询，每次都是 的查表操作。
  • 空间复杂度：。需要两个大小约为 N 的数组来存储质数表和前缀和。