首页 > 代码库 > hdu5901 Count primes(大素数模版)

hdu5901 Count primes(大素数模版)

题意:

1——n(10^11)的素数个数

思路:

参考:http://blog.csdn.net/chaiwenjun000/article/details/52589457

第一个O(n^(3/4))

/* ***********************************************Author        :devil************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <stack>#include <map>#include <string>#include <cmath>#include <stdlib.h>#define inf 0x3f3f3f3f#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate<class T>inline void rd(T &x){char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-0;c=getchar();}}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int mod=1e9+7;const int N=310;LL f[340000],g[340000],n;void init(){    LL i,j,m;    for(m=1;m*m<=n;m++) f[m]=n/m-1;    for(i=1;i<=m;i++) g[i]=i-1;    for(i=2;i<=m;i++)    {        if(g[i]==g[i-1]) continue;        for(j=1;j<=min(m-1,n/i/i);j++)        {            if(i*j<m) f[j]-=f[i*j]-g[i-1];            else f[j]-=g[n/i/j]-g[i-1];        }        for(j=m;j>=i*i;j--) g[j]-=g[j/i]-g[i-1];    }}int main(){    while(~scanf("%lld",&n))    {        init();        cout<<f[1]<<endl;    }    return 0;}

第二个O(n^(2/3))

/* ***********************************************Author        :devil************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <stack>#include <map>#include <string>#include <cmath>#include <stdlib.h>#define inf 0x3f3f3f3f#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate<class T>inline void rd(T &x){char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-0;c=getchar();}}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int mod=1e9+7;const int N=5e6+2;bool np[N];int prime[N],pi[N];int getprime(){    int cnt=0;    np[0]=np[1]=1;    pi[0]=pi[1]=0;    for(int i=2;i<N;i++)    {        if(!np[i]) prime[++cnt]=i;        pi[i]=cnt;        for(int j=1;j<=cnt&&i*prime[j]<N;j++)        {            np[i*prime[j]]=1;            if(i%prime[j]==0) break;        }    }    return cnt;}const int M=7;const int PM=2*3*5*7*11*13*17;int phi[PM+1][M+1],sz[M+1];void init(){    getprime();    sz[0]=1;    for(int i=0;i<=PM;i++) phi[i][0]=i;    for(int i=1;i<=M;i++)    {        sz[i]=prime[i]*sz[i-1];        for(int j=1;j<=PM;j++) phi[j][i]=phi[j][i-1]-phi[j/prime[i]][i-1];    }}int sqrt2(LL x){    LL r=(LL)sqrt(x-0.1);    while(r*r<=x) r++;    return int(r-1);}int sqrt3(LL x){    LL r=(LL)cbrt(x-0.1);    while(r*r*r<=x) r++;    return int(r-1);}LL getphi(LL x,int s){    if(s==0) return x;    if(s<=M) return phi[x%sz[s]][s]+(x/sz[s])*phi[sz[s]][s];    if(x<=prime[s]*prime[s]) return pi[x]-s+1;    if(x<=prime[s]*prime[s]*prime[s]&&x<N)    {        int s2x=pi[sqrt2(x)];        LL ans=pi[x]-(s2x+s-2)*(s2x-s+1)/2;        for(int i=s+1;i<=s2x;i++) ans+=pi[x/prime[i]];        return ans;    }    return getphi(x,s-1)-getphi(x/prime[s],s-1);}LL getpi(LL x){    if(x<N) return pi[x];    LL ans=getphi(x,pi[sqrt3(x)])+pi[sqrt3(x)]-1;    for(int i=pi[sqrt3(x)]+1,ed=pi[sqrt2(x)];i<=ed;i++) ans-=getpi(x/prime[i])-i+1;    return ans;}LL lehmer_pi(LL x){    if(x<N) return pi[x];    int a=(int)lehmer_pi(sqrt2(sqrt2(x)));    int b=(int)lehmer_pi(sqrt2(x));    int c=(int)lehmer_pi(sqrt3(x));    LL sum=getphi(x,a)+(LL)(b+a-2)*(b-a+1)/2;    for(int i=a+1;i<=b;i++)    {        LL w=x/prime[i];        sum-=lehmer_pi(w);        if(i>c) continue;        LL lim=lehmer_pi(sqrt2(w));        for(int j=i;j<=lim;j++) sum-=lehmer_pi(w/prime[j])-(j-1);    }    return sum;}int main(){    init();    LL n;    while(~scanf("%lld",&n))    {        printf("%lld\n",lehmer_pi(n));    }    return 0;}

 

hdu5901 Count primes(大素数模版)