题目名称是吸引你点进来的
实际上该题还是很水的
区间质数个数
一行两个整数 询问次数n，范围m
接下来n行，每行两个整数 l,r 表示区间
输出格式：对于每次询问输出个数 t，如l或r?[1,m]输出 Crossing the line
2 5 1 3 2 6
2 Crossing the line
【数据范围和约定】
对于20%的数据 1<=n<=10 1<=m<=10
对于100%的数据 1<=n<=1000 1<=m<=1000000 -10^9<=l<=r<=10^9 1<=t<=1000000
思路：本题可用欧拉筛+前缀和解决。输入范围m后用欧拉筛筛出一个素数表，再用前缀和数组sum[i]维护[2，i]的素数个数。所以[l,r]的素数个数为sum[r]-sum[l-1]。
若l<1||r>m时会越界，这时输出Crossing the line。
AC Code：
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 typedef long long ll; 5 const int sz=1000000+10; 6 ll pri[sz],sum[sz]; 7 bool vis[sz]; 8 int n,m,tot; 9 void euler() 10 { 11 vis[0]=vis[1]=1; 12 for(int i=2;i<=m;i++) 13 { 14 if(!vis[i]) 15 { 16 pri[++tot]=i; 17 } 18 for(int j=1;j<=tot&&i*pri[j]<=m;j++) 19 { 20 vis[i*pri[j]]=1; 21 if(i%pri[j]==0) break; 22 } 23 } 24 sum[0]=sum[1]=0; 25 for(int i=2;i<=m;i++) 26 { 27 if(!vis[i]) sum[i]=sum[i-1]+1; 28 else sum[i]=sum[i-1]; 29 } 30 } 31 int main() 32 { 33 scanf("%d%d",&n,&m); 34 euler(); 35 while(n--) 36 { 37 int l,r; 38 scanf("%d%d",&l,&r); 39 if(l<1||r>m) 40 { 41 printf("Crossing the line\n"); 42 continue; 43 } 44 ll ans=sum[r]-sum[l-1]; 45 printf("%lld\n",ans); 46 } 47 return 0; 48 }
洛谷 P1865 A % B Problem (欧拉筛+前缀和)
原文：http://www.cnblogs.com/Loi-Brilliant/p/7912768.html