5458. 【NOIP2017提高A组冲刺11.7】质数

5458. 【NOIP2017提高A组冲刺11.7】质数
(File IO): input:prime.in output:prime.out

Time Limits: 1000 ms Memory Limits: 524288 KB Detailed Limits

Description

小X 是一位热爱数学的男孩子，在茫茫的数字中，他对质数更有一种独特的情感。小X 认为，质数是一切自然数起源的地方。
在小X 的认知里，质数是除了本身和1 以外，没有其他因数的数字。
但由于小X 对质数的热爱超乎寻常，所以小X 同样喜欢那些虽然不是质数，但却是由两个质数相乘得来的数。
于是，我们定义，一个数是小X 喜欢的数，当且仅当其是一个质数，或是两个质数的乘积。
而现在，小X 想要知道，在L 到R 之间，有多少数是他喜欢的数呢？

Input

第一行输入一个正整数Q，表示询问的组数。
接下来Q 行。包含两个正整数L 和R。保证L≤R。

Output

输出Q 行，每行一个整数，表示小X 喜欢的数的个数。

Sample Input

输入1：

1

1 6

输入2：

10

282 491

31 178

645 856

227 367

267 487

474 697

219 468

582 792

315 612

249 307

输入3：

10

20513 96703

15236 86198

23185 78205

40687 48854

42390 95450

63915 76000

36793 92543

35347 53901

44188 76922

82177 90900

Sample Output

输出1：

5

样例1解释：

6以内的质数有2,3,5，而4=2*2,6=2*3。因此2,3,4,5,6都是小X 喜欢的数，而1 不是。

输出2：

97

78

92

65

102

98

114

90

133

29

输出3：

24413

23001

17784

2669

16785

3833

17712

6028

10442

2734

做法：当我们使用线性筛的时候，会发现和本题奇妙的契合，emmm，然后跑前缀和直接输出答案。

#include <cstdio>

#include <cstring>

#include <iostream>

#define N 10000020

using namespace std;

int q, zs[N / ], qzh[N], n;

bool b[N], v[N];

void Pre_work()

{

    memset(qzh, , sizeof(qzh));

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

    {

        if (!b[i])

        {

            zs[++zs[]] = i;

            v[i] = ;

            for (int j = ; j <= zs[]; j++)

                if (i * zs[j] > N - )    break;

                else v[i * zs[j]] = , b[i * zs[j]] = ;

        }

        else

        {

            for (int j = ; j <= zs[]; j++)

                if (i * zs[j] > N - )    break;

                else b[i * zs[j]] = ;

        }

    }

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

        qzh[i] += qzh[i - ] + v[i];

}

int main()

{

    freopen("prime.in", "r", stdin);

    freopen("prime.out", "w", stdout);

    Pre_work();

    scanf("%d", &n);

    int x, y;

    for (; n; n--)

    {

        scanf("%d%d", &x, &y);

        printf("%d\n", qzh[y] - qzh[x - ]);

    }

}

质数