给定T组询问，每次询问一个区间[l,r]中的质数个数

数据范围

1≤T≤10^6^

1≤l≤r≤10^6^

输入格式:

第一行输入一个整数T，代表询问次数, 接下来有T行，每行有两个数l,r代表询问区间.

输出格式:

输出T行,表示每组询问的结果.

输入样例:

1
2
3
2
1 10
10 20

输出样例:

1
2
4
4

样例解释：110中有4个质数（2，3，5，7），1020中有4个质数（11，13，17，19）

思路

埃氏筛法/线性筛法，都可以

埃氏筛：若一个数是素数，那么它的2倍、3倍、4倍。。。肯定不是素数，依据这个特性筛选出素数

book数组存放该数是否是素数，sum[i]数组记录小于等于i的素数个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>

using namespace std;
constexpr int MAX_SIZE = 1e6 + 1;

bool book[MAX_SIZE];//true不是素数，false是素数。先假设所有数都是素数
int sum[MAX_SIZE];//sum[i]记录1~i的素数个数

void func() { //埃氏素数筛
    book[1] = true;
    for(int i = 2; i <= MAX_SIZE; i++) {
        if(!book[i]) { //i是素数
            for(int j = 2 * i; j <= MAX_SIZE; j += i) { //它的倍数肯定不是素数
                book[j] = true;
            }
        }
    }
}

int main() {
    int t;
    scanf("%d", &t);
    func();
    sum[0] = 0;
    for(int i = 1; i <= MAX_SIZE; i++) { //记录sum
        sum[i] = sum[i - 1] + !book[i];
    }
    while(t--) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", sum[b] - sum[a - 1]);
    }
    return 0;
}