顶
by van能的搞事德M @ 2019-03-31 14:42:14
你这用户名还敢发帖子？
by Tyrion_Lannister @ 2019-03-31 14:43:42
code of 线性筛素数法:
```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;
}
}
```
图形表示为：
code of 优化：
```c
#include <bits/stdc++.h>
using namespace std;
int a,b[1000001],n,m;
inline int zhi(int x){
int i;
if(x==1)return 0;
else for(i=2;i<=sqrt(x);i++)if(x%i==0)return 0;
return 1;
}
inline void shu( ){
int i;
b[1]=b[0]=0;
for(i=2;i<=1000000;i++)
if(zhi(i)==0)b[i]=b[i-1];
else b[i]=b[i-1]+1;
}
int main( ){
int num=0,i,j,k,x,y;
shu( );
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++){
num=0;
scanf("%d %d",&x,&y);
if(x<1||y>m){printf("Crossing the line\n");continue;}
else printf("%d\n",b[y]-b[x-1]);
}
}
```
~~我还是太弱了，优化弄了半小时~~
~~给个赞嘛~~
by Space_Gold_Trash @ 2019-04-21 23:01:23
@[取什么名字](/user/117658) xiexie！！！！！
太太太牛啦啦啦啦
by Big_Black_Dick @ 2019-12-04 18:13:41