@[Roll_SKY_da_shen](/space/show?uid=175011) 请使用线性筛+前缀和，您的方法时间复杂度过高了
by Celestial_Scarlet @ 2019-04-20 14:47:04
看一下我的吧：
```cpp
#include <cstdio>
#define maxn 1000005
using namespace std;
int f[maxn];
bool IsPrime[maxn];
void initialise() {
for(int i = 2; i <= maxn; ++i)
IsPrime[i] = true;
}
void Ai_Prime() {
initialise();
f[1] = 0;
for(int i = 2; i <= maxn; ++i) {
if(IsPrime[i]) {
f[i] = f[i - 1] + 1;
for(int j = 2 * i; j <= maxn; j += i)
IsPrime[j] = false;
} else
f[i] = f[i - 1];
}
}
int main() {
Ai_Prime();
int n, m;
scanf("%d%d", &n, &m);
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 {
int ans = f[r] - f[l - 1];
printf("%d\n", ans);
}
}
return 0;
}
```
by Eason_AC @ 2019-04-20 15:09:57
我做的：
```c
#include<bits/stdc++.h>
using namespace std;
bool f[1000001]={0},dis[1000001]={0};
inline void Jack(int m){
int i,j,k;
for(i=2;i<=m;i++){
if(dis[i])continue;
f[i]=1;
k=i*2;
while(k<=m){
dis[k]=1;
k+=i;
}
}
} //线性筛
int main( ){
std::ios::sync_with_stdio(false);
int n,m,i,l,r;
cin>>n>>m;
Jack(m);
int ans[m+1];
ans[1]=ans[0]=0;
for(i=2;i<=m;i++)if(f[i])ans[i]=ans[i-1]+1;else ans[i]=ans[i-1];
for(i=1;i<=n;i++){
cin>>l>>r;
if(l<1||r>m)cout<<"Crossing the line"<<endl;
else cout<<ans[r]-ans[l-1]<<endl;
}
}
```
线性筛大致原理：
很容易实现的，并不特别难，就可以求出1-m之间的所有素数
然后就好做了
by Space_Gold_Trash @ 2019-04-20 16:10:31