线性筛跑的太慢
于是来介绍黑科技了。
MEISSEL-LEHMER算法
原理：我们预处理出N^(2/3)以内的素数
然后对于询问，我们可以计算出1-N之内，不能被2-N^(1/3)的质数整除的数字个数。
这个东西我们用f[i][j]表示,则有f[i][j]=f[i][j-1]-f[i/pri[j]][j-1]且f[i][0]=i;
同时有f[i][j]=max(0,(1-i)质数个数-j+1)
然后我们预处理出i<=100000,j<=70的f数组，剩下直接递归
然后我们+2-N^(1/3)的质数个数-1，称之为伪素数。
可以发现此时仍有合数，但一定是两个大于N^(1/3)次的素数相乘。
我们枚举较小的素数，可以计算出较大素数范围。
然后剩下的就是真·素数了。
时间,空间复杂度O（N^（2/3））
‘’‘
```cpp
#include<bits/stdc++.h>
#define N 216000
#define ll long long
using namespace std;
int mn[N],pri[N/10],fl[N];
int tot,cnt,num,n;
int f[20005][55];
int inf=2e9;
int dp(int x,int y){
if (x<=20000&&y<=50) return f[x][y];
if (x==0||y==0) return x;
if (1ll*pri[y]*pri[y]>=x&&x<N) return max(0,mn[x]-y);
return dp(x,y-1)-dp(x/pri[y],y-1);
}
void pre(){
for (int i=2;i<N;i++){
if (!fl[i]) pri[++tot]=i;
for (int j=1;i*pri[j]<N&&j<=tot;j++){
fl[i*pri[j]]=1;
if (i%pri[j]==0) break;
}
}
for (int i=1;i<N;i++)
mn[i]=(cnt+=1-fl[i]);
for (int i=1;i<=20000;i++) f[i][0]=i;
for (int i=1;i<=20000;i++)
for (int j=1;j<=50;j++)
f[i][j]=f[i][j-1]-f[i/pri[j]][j-1];
}
int power(int x,int y){
int s=1;
while (y!=0){
if (y&1){
if (s>=inf/x) s=inf;
else s=s*x;
}
y/=2;
if (x>=inf/x) x=inf;
else x=x*x;
}
return s;
}
int yroot(ll x,int y){
int l=2,r=6666,ans=1;
while (l<=r){
int mid=(l+r)/2;
if (power(mid,y)<=x) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
int work(int m){
if (m<N) return mn[m]-1;
int y=yroot(m,3),n=mn[y];
int ans=dp(m,n)+n-1;
for (n++;pri[n]*pri[n]<=m;n++)
ans-=mn[m/pri[n]]-mn[pri[n]]+1;
return ans;
}
int main(){
pre();
scanf("%d",&n);
printf("%d\n",work(n));
}
```
‘’‘