hdu5901 Count primes（大素数模版）-白红宇

hdu5901 Count primes（大素数模版）

阅读量：7239 次

发布时间：2019-06-29

本文共 2376 字，大约阅读时间需要 7 分钟。

题意：

1——n（10^11）的素数个数

思路：

参考：http://blog.csdn.net/chaiwenjun000/article/details/52589457

第一个O（n^(3/4)）

/* ***********************************************Author        :devil************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #define inf 0x3f3f3f3f#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate
                 
                  inline void rd(T &x){ char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-'0';c=getchar();}}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int mod=1e9+7;const int N=310;LL f[340000],g[340000],n;void init(){ LL i,j,m; for(m=1;m*m<=n;m++) f[m]=n/m-1; for(i=1;i<=m;i++) g[i]=i-1; for(i=2;i<=m;i++) { if(g[i]==g[i-1]) continue; for(j=1;j<=min(m-1,n/i/i);j++) { if(i*j
                  
                   =i*i;j--) g[j]-=g[j/i]-g[i-1]; }}int main(){ while(~scanf("%lld",&n)) { init(); cout<
                   
                    <

第二个O（n^(2/3)）

/* ***********************************************Author        :devil************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #define inf 0x3f3f3f3f#define LL long long#define rep(i,a,b) for(int i=a;i<=b;i++)#define dep(i,a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate
                 
                  inline void rd(T &x){ char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-'0';c=getchar();}}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int mod=1e9+7;const int N=5e6+2;bool np[N];int prime[N],pi[N];int getprime(){ int cnt=0; np[0]=np[1]=1; pi[0]=pi[1]=0; for(int i=2;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;}int main(){ init(); LL n; while(~scanf("%lld",&n)) { printf("%lld\n",lehmer_pi(n)); } return 0;}