题解 P3912 【素数个数】

大头 · 2017-10-12 11:29:20 · 题解

线性筛跑的太慢

于是来介绍黑科技了。

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））

‘’‘

#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));
}

‘’‘