HDU 5901 大数素数计数
发布时间:2020-12-14 01:31:39 所属栏目:大数据 来源:网络整理
导读:Count primes Time Limit: 12000/6000 MS (Java/Others) ? ?Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1234 ? ?Accepted Submission(s): 679 Problem Description Easy question! Calculate how many primes between [1...n]! ? Inpu
Count primes
Time Limit: 12000/6000 MS (Java/Others) ? ?Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1234 ? ?Accepted Submission(s): 679 Problem Description Easy question! Calculate how many primes between [1...n]! ? Input Each line contain one integer n(1 <= n <= 1e11).Process to end of file. ? Output For each case,output the number of primes in interval [1...n] ? Sample Input 2 3 10 ? Sample Output 1 2 4 模板题,代码 using namespace std; #include<cstdio> #include<cmath> const long long N = 5e6 + 2; bool np[N]; long long prime[N]; long long pi[N]; long long getprime() { long long cnt=0; np[0]=np[1]=true; pi[0]=pi[1]=0; for(long long i=2; i<N; ++i) { if(!np[i]) { prime[++cnt]=i; } pi[i]=cnt; for(long long j=1; j<=cnt&&i*prime[j]<N; ++j) { np[i*prime[j]]=true; if(i%prime[j]==0) break; } } return cnt; } const long long M=7; const long long PM=2*3*5*7*11*13*17; long long phi[PM+1][M+1],sz[M+1]; void init() { getprime(); sz[0]=1; for(long long i=0; i<=PM; ++i) { phi[i][0]=i; } for(long long i=1; i<=M; ++i) { sz[i]=prime[i]*sz[i-1]; for(long long j=1; j<=PM; ++j) { phi[j][i]=phi[j][i-1]-phi[j/prime[i]][i-1]; } } } long long sqrt2(long long x) { long long r=(long long )sqrt(x-0.1); while(r*r<=x) ++r; return (r-1); } long long sqrt3(long long x) { long long r=(long long )cbrt(x-0.1); while(r*r*r<=x) ++r; return (r-1); } //long long getphi(long long 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)]; // long long 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); //} long long getphi(long long 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)]; long long 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); } long long getpi(long long x) { if(x<N) return pi[x]; long long ans=getphi(x,pi[sqrt3(x)])+pi[sqrt3(x)]-1; for(long long i=pi[sqrt3(x)]+1,ed=pi[sqrt2(x)]; i<=ed; ++i) ans-=getpi(x/prime[i])-i+1; return ans; } long long suan(long long x) { if(x<N) return pi[x]; long long a=(long long)suan(sqrt2(sqrt2(x))); long long b=(long long)suan(sqrt2(x)); long long c=(long long)suan(sqrt3(x)); long long sum=getphi(x,a)+(long long)(b+a-2)*(b-a+1)/2; for(long long i=a+1; i<=b; i++) { long long w=x/prime[i]; sum-=suan(w); if(i>c) continue; long long lim=suan(sqrt2(w)); for(long long j=1; j<=lim; j++) sum-=suan(w/prime[j])-(j-1); } return sum; } int main() { init(); long long n; while(~scanf("%lld",&n)) printf("%lldn",suan(n)); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |