#include<bits/stdc++.h> #define ll long long #define xh(a,b,c) for(int a=b;a<=c;a++) #define int long long #define maxn 1000000 using namespace std; int n,a[1000010],x,y,f[1000010]; vector<int> v; signed main(){ a[1]=1; cin>>n; for(int i=2;i<=maxn;i++)if(!a[i])for(int j=2;j<=maxn/i;j++)a[i*j]=1; for(int i=1;i<=maxn;i++)f[i]=f[i-1]+!a[i]; for(int i=1;i<=n;i++){ cin>>x>>y; v.push_back(f[y]-f[x-1]); } for(int i=0;i<v.size();i++)cout<<v[i]<<'\n'; return 0; }

统计素数解题报告：

因为此题数据有10^6所以要用线型筛，比普通的筛法快，代码如下

for(int i=2; i<=1000000; i++)//开到头

{

	if(b[i]) a[++l]=i;

	for(int k=1; k<=l&&ia[k]<=1000000; k++)

        { 

   		b[i*a[k]]=0;

                if(i%a[k]==0) break;

        }

   s[i]=s[i-1];

   if(b[i]) s[i]++;

}

又因为x和y比较大，所以可以一边求素数一边用前缀和，改良后代码如下

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

{ 

	if(b[i]) a[++l]=i; 

   for(int k=1; k<=l&&ia[k]<=1000000; k++) 

   { 

   		b[ia[k]]=0;

      if(i%a[k]==0) break;

   } 

   s[i]=s[i-1];//s为前缀和数组 

   if(b[i]) s[i]++; 

}

然后就可以一边输入一边输出了

for(int i=1; i<=n; i++)

{ 

	cin>>x>>y;

   cout<<s[y]-s[x-1]<<endl;//因为是x~y，所以是s[y]减去x的后一个s[x-1] }

总体代码为

#include <bits/stdc++.h>

using namespace std;

long a[1000000],s[1000000];

bool b[1000010];

int main()

{

	long n,l=0,x,y;

   cin>>n;

   memset(b,1,sizeof b);

   b[1]=0;

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

   {

   		if(b[i]) a[++l]=i;

    	for(int k=1; k<=l&&ia[k]<=1000000; k++)

    	{

    		b[i*a[k]]=0;

    		if(i%a[k]==0) break;

    	}

    	s[i]=s[i-1];

    	if(b[i]) s[i]++;

   }

   for(int i=1; i<=n; i++)

   {

   		cin>>x>>y;

      cout<<s[y]-s[x-1]<<endl;

   }

   return 0;

  }

请参考此处