HDU 5901 大数素数计数
Count primes
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); / |