一、检查n是否为素数

最简单思路：所有可能的因数全部试一遍。

  

   

    

     

    
    

     

      int gg(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i=2;i<n;i++){
     
    
   

    

     

    
    

     
 if((n%i)==0)return 0;//有因数就不是素数咯
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 1;
     
    
   

    

     

    
    

     

      }
     
    
  
 

进一步思考：没必要枚举所有的数，每一个小于n^(1/2)的因数i，一定有一个大于n^(1/2)的因数j与之对应，也就是i*j=n，所以枚举小于等于n^(1/2)的因数即可

  

   

    

     

    
    

     

      int gg(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int i=2;i*i<=n;i++){
     
    
   

    

     

    
    

     
 if((n%i)==0)return 0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 1;
     
    
   

    

     

    
    

     

      }
     
    
  
 

二、约数枚举

 上面已经说过，不需要枚举所有因数，枚举出某小因数以后算出对应的大因数即可。

  

   

    

     

    
    

     

      vector<int> gg(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 vector<int> a;
     
    
   

    

     

    
    

     
 for(int i=2;i*i<=n;i++){
     
    
   

    

     

    
    

     
 if((n%i)==0){
     
    
   

    

     

    
    

     

       a.push_back(i);
     
    
   

    

     

    
    

     
 if((n/i)!=i)a.push_back(n/i);//根号n的情况不要重复添加
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return a;
     
    
   

    

     

    
    

     

      }
     
    
  
 

三、埃氏筛法

 只对一个整数操作，O(N)，已经足够了，如果对许多整数进行素性检测，还有更高效的算法，比如埃氏筛法。

问题：枚举n以内所有素数

操作：先把所有整数列出来，然后把2的倍数全部剔除，然后是三的，以此类推，遍历所有素数，把倍数全部划去。

对于每个数字i，如果没被划去，他一定是素数，因为他不是任何2到i-1数字的倍数。然后就开始划它的倍数就好。

  

   

    

     

    
    

     

      int a[maxx];
     
    
   

    

     

    
    

     

      int b[maxx+1];
     
    
   

    

     

    
    

     

      int gg(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int p=0;//记录素数个数
     
    
   

    

     

    
    

     
 for(int i=0;i<n+1;i++)b[i]=1;
     
    
   

    

     

    
    

     

       b[0]=0;
     
    
   

    

     

    
    

     

       b[1]=0;
     
    
   

    

     

    
    

     
 //准备完毕
     
    
   

    

     

    
    

     
 for(int i=2;i<=n;i++){
     
    
   

    

     

    
    

     
 if(b[i]){
     
    
   

    

     

    
    

     

       a[p++]=i;//记录素数和个数
     
    
   

    

     

    
    

     
 for(int j=2*i;j<=n;j+=i)b[j]=0;//剔除倍数
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return p;//返回素数个数
     
    
   

    

     

    
    

     

      }
     
    
  
 

四、区间筛法

 给定整数a和b，请问区间[a,b)内有多少个素数？ 

思路：之前说过，因为b以内合数的最小质因数一定不超过sqrt(b),如果有sqrt(b)以内的素数表的话，就可以把筛选法用在[a,b)上了,先分别做好[2,sqrt(b))的表和[a,b)的表，然后从[2,sqrt(b))的表中筛得素数的同时，也将其倍数从[a,b)的表中划去，最后剩下的就是区间[a,b)内的素数了。

  

   

    

     

    
    

     

      //不gg了，这次就来个标准一点的吧
     
    
   

    

     

    
    

     

      typedef long long ll;
     
    
   

    

     

    
    

     

      bool is_prime[maxn];
     
    
   

    

     

    
    

     

      bool is_prime_small[maxn];
     
    
   

    

     

    
    

     

      void segment_sieve(ll a,ll b) 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(ll i=0;i*i<b;++i) is_prime_small[i]=true; //初始化
     
    
   

    

     

    
    

     
 for(ll i=0;i<b-a;++i) is_prime[i]=true; //初始化，注意下标变化，为了省空间
     
    
   

    

     

    
    

     
 for(ll i=2;i*i<b;++i) {
     
    
   

    

     

    
    

     
 if(is_prime_small[i]) {
     
    
   

    

     

    
    

     
 for(ll j=2*i;j*j<b;j+=i) is_prime_small[j]=false;  //筛选[2,sqrt(b));
     
    
   

    

     

    
    

     
 //(a+i-1)/i得到最接近a的i的倍数，最低是i的2倍，然后筛选
     
    
   

    

     

    
    

     
 for(ll j=max(2LL,(a+i-1)/i)*i;j<b;j+=i) is_prime[j-a]=false;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

五、线性实现

筛法很多数被处理了不止1遍，比如6，在素数为2的时候处理1次，为3时候又处理一次，因此又造成了不必要处理。O(nloglogn)已经基本可以满足一般需要了。

本代码保证每个合数只会被它的最小质因数筛去，因此每个数只会被标记一次，所以时间复杂度是O(n)

证明略

话不多说，上板子

  

   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #define MAXN 100005
     
    
   

    

     

    
    

     

      #define MAXL 1299710
     
    
   

    

     

    
    

     

      int prime[MAXN];
     
    
   

    

     

    
    

     

      int check[MAXL];
     
    
   

    

     

    
    

     

      int tot = 0;
     
    
   

    

     

    
    

     

      memset(check, 0, sizeof(check));
     
    
   

    

     

    
    

     

      for (int i = 2; i < MAXL; ++i)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(!check[i])prime[tot++] = i;
     
    
   

    

     

    
    

     
 for (int j = 0; j < tot; ++j)//****************************************
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if (i * prime[j] > MAXL)break;//*******************
     
    
   

    

     

    
    

     

       check[i*prime[j]] = 1;
     
    
   

    

     

    
    

     
 if (i % prime[j] == 0)break;//******
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

素数基本就这些内容咯。。。。

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/81486370