这道题难道不是用线性筛吗?
两层循环也没有TLE啊,为什么会WA?
代码:
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
const int N=1e6+5;
int n,m;
int l,r;
int f[N],p[N],c;
int ans;
void ola(int m){
for(int i=2;i<=m;i++){
if(f[i]==0){
p[++c]=i;
}
for(int j=1;p[j]*i<=m&&j<=c;j++){
f[p[j]*i]=1;
if(i%p[j]==0) break;
}
}
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n>>m;
ola(m);
for(int k=1;k<=n;k++){
cin>>l>>r;
ans=0;
if(l<1||r>m){
cout<<"Crossing the line"<<endl;
continue;
}
for(int i=1;i<c;i++){
if(p[i]>r) break;
if(p[i]>l) ans++;
}
cout<<ans<<endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
实在搞不懂