Question

哪位大神帮个忙（c++）？

MIKE曾经是大名鼎鼎的数学家，他老年痴呆以后依然对数论很痴迷。他喜欢不停询问别人从a到b之间(包含a和b)共有多少个质数。如果你全部答对，他就会心一笑。为了让MIKE能安度晚年，你写了一个程序。

输入格式
输入第一行为m，代表共m条询问。之后m行为询问的细节，每行包含a和b两个正整数，a<=b<=100000，m<=100000。
输出格式
输出共一行，包含m个答案，由空格分开。

Answer 1

首先根据质数筛法，用数组prime标记0~100000中的所有质数，prime[i]==1表示i为质数

然后将prime数组转为前缀和数组，即令prime[i]等于prime[0]~prime[i]之和

表示0~i中的质数个数，这样任意区间[a,b]中的质数个数就等于prime[b]-prime[a-1]

相应C++代码和运行结果如下：

如图输出了1~30、1~100000之间的质数个数分别为10和9592

附源码：

#include <iostream>

#define N 100000

using namespace std;

int prime[N + 1]; // 标记每个数是否为质数，初值为0

int main() {

    for (int i = 2; i <= N; ++i)

        prime[i] = 1; // 初始化2~N都为质数

    for (int i = 2; i * i <= N; ++i) { // 从最小的质数2开始

        if (prime[i] == 1) // 若i为质数

            for (int j = i * i; j <= N; j += i) // 标记i的所有倍数j为合数

                prime[j] = 0; // i*i之前的倍数肯定已标记过

    } 

    for (int i = 1; i <= N; ++i)  // 转为前缀和

        prime[i] += prime[i - 1]; // 表示[0~i]中的质数个数

    int m, a, b;

    cin >> m;

    int ans[m]; // 保存m组结果

    for (int i = 0; i < m; ++i) {

        cin >> a >> b;

        ans[i] = prime[b] - prime[a - 1];

    }

    for (int i = 0; i < m - 1; ++i)

        cout << ans[i] << " ";

    cout << ans[m - 1] << endl;

    return 0;

}