爆炸快求1~n有多少素数

这个求一千亿以内的素数大约用6780ms

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

using namespace std;

__int64  *primarr, *v;

__int64  q = , p = ;

void Out(__int64 a)    //输出外挂

{

    if(a>)

        Out(a/);

    putchar(a%+'');

}

__int64 Scan()     //输入外挂

{

    __int64 res=,ch,flag=;

    if((ch=getchar())=='-')

        flag=;

    else if(ch>=''&&ch<='')

        res=ch-'';

    while((ch=getchar())>=''&&ch<='')

        res=res*+ch-'';

    return flag?-res:res;

}

//π(n)

__int64  pi(__int64  n, __int64  primarr[], __int64  len)

{

    __int64  i = , mark = ;

    for (i = len - ; i > ; i--) {

        if (primarr[i] < n) {

            mark = ;

            break;

        }

    }

    if (mark)

        return i + ;

    return ;

}

//Φ(x,a)

__int64  phi(__int64  x, __int64  a, __int64  m)

{

    if (a == m)

        return (x / q) * p + v[x % q];

    if (x < primarr[a - ])

        return ;

    return phi(x, a - , m) - phi(x / primarr[a - ], a - , m);

}

__int64  prime(__int64  n)

{

    char *mark;

    __int64  mark_len;

    __int64  count = ;

    __int64  i, j, m = ;

    __int64  sum = , s = ;

    __int64  len, len2, len3;

    mark_len = (n < ) ?  : ((__int64 )exp(2.0 /  * log(n)) + );

    //筛选n^(2/3)或n内的素数

    mark = (char *)malloc(sizeof(char) * mark_len);

    memset(mark, , sizeof(char) * mark_len);

    for (i = ; i < (__int64 )sqrt(mark_len); i++) {

        if (mark[i])

            continue;

        for (j = i + i; j < mark_len; j += i)

            mark[j] = ;

    }

    mark[] = mark[] = ;

    //统计素数数目

    for (i = ; i < mark_len; i++)

        if (!mark[i])

            count++;

    //保存素数

    primarr = (__int64  *)malloc(sizeof(__int64 ) * count);

    j = ;

    for (i = ; i < mark_len; i++)

        if (!mark[i])

            primarr[j++] = i;

    if (n < )

        return pi(n, primarr, count);

    //n^(1/3)内的素数数目

    len = pi((__int64 )exp(1.0 /  * log(n)), primarr, count);

    //n^(1/2)内的素数数目

    len2 = pi((__int64 )sqrt(n), primarr, count);

    //n^（2/3)内的素数数目

    len3 = pi(mark_len - , primarr, count);

    //乘积个数

    j = mark_len - ;

    for (i = (__int64 )exp(1.0 /  * log(n)); i <= (__int64 )sqrt(n); i++) {

        if (!mark[i]) {

            while (i * j > n) {

                if (!mark[j])

                    s++;

                j--;

            }

            sum += s;

        }

    }

    free(mark);

    sum = (len2 - len) * len3 - sum;

    sum += (len * (len - ) - len2 * (len2 - )) / ;

    //欧拉函数

    if (m > len)

        m = len;

    for (i = ; i < m; i++) {

        q *= primarr[i];

        p *= primarr[i] - ;

    }

    v = (__int64  *)malloc(sizeof(__int64 ) * q);

    for (i = ; i < q; i++)

        v[i] = i;

    for (i = ; i < m; i++)

        for (j = q - ; j >= ; j--)

            v[j] -= v[j / primarr[i]];

    sum = phi(n, len, m) - sum + len - ;

    free(primarr);

    free(v);

    return sum;

}

int main()

{

    __int64  n;

    //int h;

    ///clock_t start, end;

    //freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);

    //std::ios::sync_with_stdio(false);

    while(~scanf("%lld",&n))

    {

        if(n==)

        {

            printf("1\n");

            continue;

        }

        //p=1;

        //q=1;

        //start = clock();

        Out(prime(n+));

        printf("\n");

        //end = clock() - start;

        //printf("用时%lfms\n",(double)end);

    }

    return ;

}

这个完全就是爆炸了

#include <bits/stdtr1c++.h>

#define MAXN 100    // pre-calc max n for phi(m, n)

#define MAXM 100010 // pre-calc max m for phi(m, n)

#define MAXP 666666 // max primes counter

#define MAX 10000010    // max prime

#define clr(ar) memset(ar, 0, sizeof(ar))

#define read() freopen("lol.txt", "r", stdin)

#define dbg(x) cout << #x << " = " << x << endl

// compressed bool flag for sieve prime. (i >> 1) because even numbers are omitted.

#define setbit(ar, i) (((ar[(i) >> 6]) |= (1 << (((i) >> 1) & 31))))

#define chkbit(ar, i) (((ar[(i) >> 6]) & (1 << (((i) >> 1) & 31))))

#define isprime(x) (( (x) && ((x)&1) && (!chkbit(ar, (x)))) || ((x) == 2))

using namespace std;

namespace pcf{

    long long dp[MAXN][MAXM];

    unsigned int ar[(MAX >> ) + ] = {};

    int len = , primes[MAXP], counter[MAX];

    void Sieve(){

        setbit(ar, ), setbit(ar, );

        for (int i = ; (i * i) < MAX; i++, i++){

            if (!chkbit(ar, i)){

                int k = i << ;

                for (int j = (i * i); j < MAX; j += k) setbit(ar, j);

            }

        }

        for (int i = ; i < MAX; i++){

            counter[i] = counter[i - ];

            if (isprime(i)) primes[len++] = i, counter[i]++;

        }

    }

    void init(){

        Sieve();

        for (int n = ; n < MAXN; n++){

            for (int m = ; m < MAXM; m++){

                if (!n) dp[n][m] = m;

                else dp[n][m] = dp[n - ][m] - dp[n - ][m / primes[n - ]];

            }

        }

    }

    long long phi(long long m, int n){

        if (n == ) return m;

        if (primes[n - ] >= m) return ;

        if (m < MAXM && n < MAXN) return dp[n][m];

        return phi(m, n - ) - phi(m / primes[n - ], n - );

    }

    long long Lehmer(long long m){

        if (m < MAX) return counter[m];

        long long w, res = ;

        int i, a, s, c, x, y;

        s = sqrt(0.9 + m), y = c = cbrt(0.9 + m);

        a = counter[y], res = phi(m, a) + a - ;

        for (i = a; primes[i] <= s; i++) res = res - Lehmer(m / primes[i]) + Lehmer(primes[i]) - ;

        return res;

    }

}

int main(){

    pcf::init();

    long long n, res;

    while (scanf("%lld", &n) != EOF){

        printf("%lld\n", pcf::Lehmer(n));

    }

    return ;

}