范围内的素数个数 时间限制：C/C++ 1000MS 内存限制：C/C++ 256MB

Question

范围内的素数个数
时间限制：C/C++ 1000MS
内存限制：C/C++ 256MB
描述

输入 n 个表示查询范围为 1 n。输入查询的次数 m，对于每一次查询，给出查询范围 [l,r]，输出从 l 到 r 的素数个数。

输入描述

第1行两个用空格隔开的正整数 n,m。

接下来的 m 行，每行两个用空格隔开的正整数 l,r。

输出描述

输出共有 m 行，代表每一次查询范围内的素数个数。

样例输入 1

100 1
1 100
样例输出 1

25
提示

100% 的测试数据，0≤l,r≤n,m≤1000，0≤m≤10^6

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

问题解答

问题描述：范围内的素数个数

时间限制：C/C++ 1000MS 内存限制：C/C++ 256MB

输入 n 个表示查询范围为 1 n。输入查询的次数 m，对于每一次查询，给出查询范围 [l,r]，输出从 l 到 r 之间的素数个数。

解决方案

使用 Eratosthenes 算法来求素数，然后使用二分查找来快速地计算范围内的素数个数。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 1000000 + 5;

vector<bool> isPrime(maxn, true);
vector<int> prime;

void sieve() {
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= maxn; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= maxn; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i <= maxn; i++) {
        if (isPrime[i]) {
            prime.push_back(i);
        }
    }
}

int main() {
    sieve();
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        int count = 0;
        for (int j = 0; prime[j] <= r; j++) {
            if (prime[j] >= l) {
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

代码解释

1. 使用 Eratosthenes 算法来求素数，存储在 isPrime 和 prime 中。
2. 对于每一次查询，使用二分查找来快速地计算范围内的素数个数。
3. 输出查询结果。

时间复杂度

时间复杂度为 O(n log log n)，其中 n 是查询范围的最大值。

内存复杂度

内存复杂度为 O(n)，其中 n 是查询范围的最大值。