埃式筛法尽管不错，但是确实做了许多无用功，某个数可能会被重复的筛好几次，欧拉筛解决了这个方法，下面为代码：
注意理解if(i%prim[j]==0) break;
大佬讲的不错的博客，我就不做复读机了。
点我传送

void ispirm(){int cnt=0;memset(visited,true,sizeof(visited));for(int i=2;i<=maxn;i++){if(visited[i]) prim[cnt++]=i;for(int j=0;j<cnt&&prim[j]*i<=maxn;j++){visited[prim[j]*i]=false;if(i%prim[j]==0) break;}}
}

学会了欧拉筛法的话，下面有个经典例题，查询某段区间内质数的个数
题目链接：点我传送
这里用前缀和处理一下就可以再O(1)的时间复杂度情况查出了。

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 1e7;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
bool visited[maxn+10];
int prim[1000000+5];
int ans[maxn+10];
void ispirm(){int cnt=0;memset(visited,true,sizeof(visited));for(int i=2;i<=maxn;i++){if(visited[i]) prim[cnt++]=i;for(int j=0;j<cnt&&prim[j]*i<=maxn;j++){visited[prim[j]*i]=false;if(i%prim[j]==0) break;}}
}
int main()
{ispirm();int t;cin>>t;for(int i=2;i<=maxn;i++){ans[i]=ans[i-1]+visited[i];}while(t--){int x,y;scanf("%d%d",&x,&y);printf("%d\n",ans[y]-ans[x-1]);}return 0;
}