统计素数解题报告：

因为此题数据有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;

  }

请参考此处