解题报告 P1865 A % B Problem（区间质数）

题目内容

P1865

大意：求区间质数个数

解题思路

第一眼看上去想到线段树，但其实这题可以使用前缀和的思想来做，令 a_x 表示在 [1,x] 中有 a_x 个质数，当查询 [l,r] 的质数个数时，只需打印 a_r-a_{l-1} 即可。

前面要先筛出质数，由于我不会欧拉筛所以用的是埃氏筛，虽然慢了点，但是能过去。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>

int n,m;//m is the range
bool prime[1000005];
int qzh[1000005];

void make_prime()
{
    memset(prime,1,sizeof(prime));
    prime[0]=prime[1]=0;
    for(int i=2;i<=sqrt(m)+1;i++)
    {
        if(prime[i])
            for(int j=2*i;j<=m;j+=i)
                prime[j]=0;
    }
    return;
}

int main()
{
    scanf("%d %d", &n, &m);
    make_prime();//不要忘记先造质数
    for(int i=0;i<=m;i++)
    {
        qzh[i]=qzh[i-1];
        if(prime[i])
            qzh[i]++;
    }
    for(int i=1;i<=n;i++)
    {
        int l,r;
        scanf("%d %d", &l, &r);
        if(l<1||r>m)//注意判别边界
            printf("Crossing the line\n");
        else
            printf("%d\n",qzh[r]-qzh[l-1]);//输出前缀和之差
    }
    return 0;
}