这个题吧，纯属看模板好不好。。。


题意很简单，求【1，n】中的素数有多少个，n很大，1e11的范围

原来普通的数学方法构造的打表是TLE或者MLE的


Lehmer快速求素数


用这个方法呢，就可以形成一个模板类的素数打表了

思想是小数据用打表中的值输出，大数据用Lehmer的公式化归一下就可以往下递归，然后推到表格中的数值了


模板贴一下吧，链接中也有：

#include<bits/stdc++.h>
using namespace std;

#define MAXN 110
#define MAXM 10010
#define MAXP 666666
#define MAX 1000010
#define LL __int64
#define clr(arr) memset(arr,0,sizeof(arr))
#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(arr, (x)))) || ((x) == 2))

LL dp[MAXN][MAXM];
unsigned int arr[(MAX>>6)+5]={0};
int len=0,primes[MAXP],counter[MAX];

void SS(){
    setbit(arr,0);
    setbit(arr,1);
    for(int i=3;(i*i)<MAX;i++,i++)
    if (!chkbit(arr,i)){
        int k=i<<1;
        for(int j=i*i;j<MAX;j+=k)
            setbit(arr,j);
    }
    for(int i=1;i<MAX;i++){
        counter[i]=counter[i-1];
        if (isprime(i)) primes[len++]=i,counter[i]++;
    }
}

void init(){
    SS();
    for(int n=0;n<MAXN;n++)
    for(int m=0;m<MAXM;m++){
        if (!n) dp[n][m]=m;
        else dp[n][m]=dp[n-1][m]-dp[n-1][m/primes[n-1]];
    }
}

LL phi(LL m,int n){
    if (!n) return m;
    if (primes[n-1]>=m) return 1;
    if (m<MAXM&&n<MAXN) return dp[n][m];
    return phi(m,n-1)-phi(m/primes[n-1],n-1);
}

LL Lehmer(LL m){
    if (m<MAX) return counter[m];
    int s=sqrt(0.9+m);
    int y=cbrt(0.9+m);
    int a=counter[y];
    LL res=phi(m,a)+a-1;
    for(int i=a;primes[i]<=s;i++)
        res=res-Lehmer(m/primes[i])+Lehmer(primes[i])-1;
    return res;
}

int main(){
    init();
    LL n;
    while(scanf("%I64d",&n)!=EOF) printf("%I64d\n",Lehmer(n));
    return 0;
}