部分和3统计素数     时限：1s 空间：256m

统计素数(pcount)

题目描述

桐桐想统计某个区间范围里的素数，例如，A=2，B=10，则A和B之间（包括A、B）素数一共有4个，分别为：2，3，5，7。现在桐桐给出N个区间范围，问每个区间有多少个素数。请你帮助她统计一下。

输入格式

第一行一个整数 N(1<=N<=10^5)；
后有N行，每行两个整数A B(1<=A<=B<=10^6)，用空格隔开，表示一个区间范围。

输出格式

共N行，每行一个整数，对应区间范围的素数个数。

输入样例

2

2 8

1 13

输出样例

4

6

#include<bits/stdc++.h>
using namespace std;
long long jk[1000002],n,m,q,x,y,a[10000002],b[10000002];
int main(){    
	cin>>q;
    //10^6 100|00000;
	for(int i=2; i<=10000002; i++)
	{
		if(a[i]!=0)continue;
	    for(long long j=i*2; j<=10000002; j+=i) a[j]=1;
	}
	for(long long i=2; i<=10000002; i++)
	{
	    if(a[i]==0)
	    for(int j=2; ; j++)
	    {
	        if(i*j>10000002) break;
	        a[i*j]=1;
	    }
	}
	for(long long i=2; i<=10000002; i++)
	{
	    if(a[i]==0)b[i]=b[i-1]+1;
	    else if(a[i]==1) b[i]=b[i-1]+0;
	}
	/*for(long long i=1; i<=102; i++)
	{
		printf("%lld\n",b[i]);
	}*/
	for(long long i=1; i<=q; i++)
	{
		scanf("%lld%lld",&x,&y);
		printf("%lld\n",b[y]-b[x-1]);
	}
    return 0;
}