欧拉筛 筛法求素数 及其例题 时间复杂度O(n)

埃式筛法尽管不错，但是确实做了许多无用功，某个数可能会被重复的筛好几次，欧拉筛解决了这个方法，下面为代码：
注意理解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;
}