SCUT - 142 - 第n个素数

但是洲阁筛打表还是超时了，打的表不够长吧，在51nod上面要跑5s。要是快10倍得要密1000倍，根本打不出来（时间意义）。

暴力check要找的质数是不是要的那个。

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int MAXN = 7500000;

int n;

int f[MAXN + 5], p[MAXN + 5];

bool np[MAXN + 5];

ll g(ll n, int m) {

    if(!m)

        return n;

    if(m == 1)

        return n - n / 2;

    if(n <= MAXN) {

        if(f[n] <= m)

            return 1;

        if(f[(int)sqrt(n)] <= m)

            return f[n] - m + 1;

    }

    ll res = g(n, m - 1) - g(n / p[m], m - 1);

    return res;

}

bool pan(ll x) {

    ll y = sqrt(x);

    return f[y] + g(x, f[y]) - 1 >= n;

}

void init() {

    for(int i = 2; i <= MAXN; ++i) {

        if(!np[i])

            p[++p[0]] = i;

        for(int j = 1, t; j <= p[0] && (t = p[j] * i) <= MAXN; ++j) {

            np[t] = 1;

            if(i % p[j] == 0)

                break;

        }

    }

    for(int i = 2; i <= MAXN; ++i)

        f[i] = f[i - 1] + (np[i] == 0);

}

ll pcount[] = {

    373587883,

    776531401,

    1190494759,

    1611623773,

    2038074743,

    2468776129,

    2902958801,

    3340200037,

    3780008329,

    4222234741,

    4666527007,

    5112733757,

    5560695863,

    6010236857,

    6461335109,

    6913774603,

    7367575799,

    7822624247,

    8278737359,

    8736028057,

    9194418049,

    9653704481,

    10113958157,

    10575209467,

    11037271757,

    11500205947,

    11963902331,

    12428375423,

    12893587657,

    13359555403,

    13826206699,

    14293566641,

    14761538761,

    15230122499,

    15699342107,

    16169207209,

    16639648327,

    17110593779,

    17582163853,

    18054236957,

    18526876243,

    18999999247,

    19473535801,

    19947663787,

    20422213579,

    20897216723,

    21372698029,

    21848603809,

    22325014259,

    22801763489

};

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

    //freopen("Yinku.out", "w", stdout);

#endif // Yinku

    init();

    while(~scanf("%d", &n)) {

        int px = n / (int)(2e7);

        ll l = px == 0 ? 1 : pcount[px - 1], r = pcount[px], mid;

        //cout << "l=" << l << " r=" << r << endl;

        while(l < r) {

            mid = (l + r) / 2;

            if(pan(mid))

                r = mid;

            else

                l = mid + 1;

        }

        printf("%lld\n", l);

    }

}

下面的好迷惑啊；

#include<iostream>

#include<cmath>

#include<assert.h>

using namespace std;

typedef long long LINT;

LINT a,b,goal,n;

int mark[160000],prime[160000],e,bl[10000005];

LINT pn(int n)

{

    LINT s=LINT(n*(log(n)+log(log(n))-1)+n*(log(log(n))-2)/log(n)-6.0*n/1000.0);

    return s<=1?1:s;

}

inline LINT V2IDX(LINT v, LINT N, LINT Ndr, LINT nv) {

    return v >= Ndr ? (N/v - 1) : (nv - v);

}

LINT primesum(LINT N) {

    LINT *S;

    LINT *V;

    LINT r = (LINT)sqrt(N);

    LINT Ndr = N/r;

    assert(r*r <= N and (r+1)*(r+1) > N);

    LINT nv = r + Ndr - 1;

    V = new LINT[nv];

    S = new LINT[nv];

    for (LINT i=0; i<r; i++) {

        V[i] = N/(i+1);

    }

    for (LINT i=r; i<nv; i++) {

        V[i] = V[i-1] - 1;

    }

    for (LINT i=0; i<nv; i++) {

      //S[i] = V[i] * (V[i] + 1) / 2 - 1;若求素数和，使用此处

        S[i]=V[i] - 1;

      //若求素数个数使用此处

    }

    for (LINT p=2; p<=r; p++) {

        if (S[nv-p] > S[nv-p+1]) {

            LINT sp = S[nv-p+1];

            LINT p2 = p*p;

            for (LINT i=0; i<nv; i++) {

                if (V[i] >= p2) {

                //S[i] -= p* (S[V2IDX(V[i]/p, N, Ndr, nv)] - sp);若求素数和，使用此处

                    S[i] -= 1* (S[V2IDX(V[i]/p, N, Ndr, nv)] - sp);

                  //若求素数个数，使用此处

                } else {

                    break;

                }

            }

        }

    }

    return S[0];

}

int main()

{

    cin>>n;

    a=pn(n);

    if(a%2&&a>1)a=a-1;//防止预估值本身就是素数的情况，刚开始被这里坑了3个test

    b=a+7000000;

    goal=n-primesum(a);

    for(int i=2;i<=160000;i++)

    {

        if(!mark[i])

        {

            prime[++e]=i;

            for(LINT j=(LINT)i*i;j<=160000;j+=i)

            {

                mark[j]=1;

            }

        }

    }

    LINT xxx,c;

    for(int i=1;i<=e;i++)

    {

        xxx=(LINT)ceil(1.0*a/prime[i]);

        if(xxx==1) xxx++;

        for(LINT j=xxx;(c=j*prime[i])<b;j++)

        {

            bl[c-a]=1;

        }

    }

    int ans=0;

    c=b-a;

    if(a==1) ans--;

    for(int i=0;i<c;i++)

    {

        if(!bl[i]) ans++;

        if(ans==goal)

        {

            cout<<i+a<<endl;

            break;

        }

    }

    return 0;

}

Meisell-Lehmer算法计算2~n之间的素数的个数然后二分就可以了。

bool np[maxn];

int prime[maxn],pi[maxn];  

int getprime()

{

    int cnt=0;

    np[0]=np[1]=true;

    pi[0]=pi[1]=0;

    for(int i=2; i<maxn; ++i)

    {

        if(!np[i]) prime[++cnt]=i;

        pi[i]=cnt;

        for(int j=1; j<=cnt&&i*prime[j]<maxn; ++j)

        {

            np[i*prime[j]]=true;

            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<maxn)

    {

        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<maxn) 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<maxn) 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;

}

巴特西

SCUT - 142 - 第n个素数

最新文章

热门文章