Count primes

 1 #include<bits/stdc++.h> 2 using namespace std; 3  4 #define MAXN 110 5 #define MAXM 10010 6 #define MAXP 666666 7 #define MAX 1000010 8 #define LL long long int 9 #define clr(arr) memset(arr,0,sizeof(arr))10 #define setbit(ar, i) (((ar[(i) >> 6]) |= (1 << (((i) >> 1) & 31))))11 #define chkbit(ar, i) (((ar[(i) >> 6]) & (1 << (((i) >> 1) & 31))))12 #define isprime(x) (( (x) && ((x)&1) && (!chkbit(arr, (x)))) || ((x) == 2))13 14 LL dp[MAXN][MAXM];15 unsigned int arr[(MAX>>6)+5]={0};16 int len=0,primes[MAXP],counter[MAX];17 18 void SS(){19     setbit(arr,0);20     setbit(arr,1);21     for(int i=3;(i*i)<MAX;i++,i++)22     if (!chkbit(arr,i)){23         int k=i<<1;24         for(int j=i*i;j<MAX;j+=k)25             setbit(arr,j);26     }27     for(int i=1;i<MAX;i++){28         counter[i]=counter[i-1];29         if (isprime(i)) primes[len++]=i,counter[i]++;30     }31 }32 33 void init(){34     SS();35     for(int n=0;n<MAXN;n++)36     for(int m=0;m<MAXM;m++){37         if (!n) dp[n][m]=m;38         else dp[n][m]=dp[n-1][m]-dp[n-1][m/primes[n-1]];39     }40 }41 42 LL phi(LL m,int n){43     if (!n) return m;44     if (primes[n-1]>=m) return 1;45     if (m<MAXM&&n<MAXN) return dp[n][m];46     return phi(m,n-1)-phi(m/primes[n-1],n-1);47 }48 49 LL Lehmer(LL m){50     if (m<MAX) return counter[m];51     int s=sqrt(0.9+m);52     int y=cbrt(0.9+m);53     int a=counter[y];54     LL res=phi(m,a)+a-1;55     for(int i=a;primes[i]<=s;i++)56         res=res-Lehmer(m/primes[i])+Lehmer(primes[i])-1;57     return res;58 }59 60 int main(){61     init();62     LL n;63     while(scanf("%I64d",&n)!=EOF) printf("%I64d\n",Lehmer(n));64     return 0;65 }