首页 > 代码库 > 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(大素数模版)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。