LOJ6235 区间素数个数（min_25筛）

题目链接：LOJ

题目大意：看到题目名字应该都知道是啥了吧。

$1\le N\le 10^{11}$。

---

阉割版 min_25 筛。发现答案实际上就是 min_25 筛中 $g(N,pl)$ 的值。（取次数 $k=0$ 即可）

在这里再写一遍式子。（用久了应该要背了）

$g(n,0)=n-1$

$g(n,j)=\begin{cases}g(n,j-1)&p_j^2>n\\g(n,j-1)-(g(\lfloor\dfrac{n}{p_j}\rfloor,j)-(j-1))&p_j^2\le n\end{cases}$

直接算即可。时间复杂度 $O(\frac{N^{3/4}}{\log N})$。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define ROF(i,a,b) for(int i=(a);i>=(b);i--)

#define MEM(x,v) memset(x,v,sizeof(x))

ll n,w[maxn],g[maxn];

int sq,pri[maxn],pl,tot,id1[maxn],id2[maxn];

bool vis[maxn];

inline int id(ll x){return x<=sq?id1[x]:id2[n/x];}

void init(){

    sq=sqrt(n);

    FOR(i,,sq){

        if(!vis[i]) pri[++pl]=i;

        FOR(j,,pl){

            if(i*pri[j]>sq) break;

            vis[i*pri[j]]=true;

            if(i%pri[j]==) break;

        }

    }

    for(ll l=,r;l<=n;l=r+){

        r=n/(n/l);

        w[++tot]=n/l;

        if(n/l<=sq) id1[n/l]=tot;

        else id2[n/(n/l)]=tot;

        g[tot]=w[tot]-;

    }

}

void calc(){

    FOR(i,,pl) FOR(j,,tot){

        if((ll)pri[i]*pri[i]>w[j]) break;

        g[j]-=g[id(w[j]/pri[i])]-(i-);

    }

}

int main(){

    scanf("%lld",&n);

    init();

    calc();

    printf("%lld\n",g[id(n)]);

}