小于n的质数的个数(1≤n≤10^11)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll f[340000],g[340000],n;
 5 void init()
 6 {
 7     ll i,j,m;
 8     for(m=1;m*m<=n;++m)
 9         f[m]=n/m-1;
10     for(i=1;i<=m;++i)
11         g[i]=i-1;
12     for(i=2;i<=m;++i)
13     {
14         if(g[i]==g[i-1])
15             continue;
16         for(j=1;j<=min(m-1,n/i/i);++j)
17         {
18             if(i*j<m)
19                 f[j]-=f[i*j]-g[i-1];
20             else
21                 f[j]-=g[n/i/j]-g[i-1];
22         }
23         for(j=m;j>=i*i;--j)
24             g[j]-=g[j/i]-g[i-1];
25     }
26 }
27 int main()
28 {
29     scanf("%lld",&n);
30     init();
31     printf("%lld\n",f[1]);
32     return 0;
33 }