HDU 5901 大数素数计数

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);
/                        
（编辑：佛山站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!