求素数方法_怎么求素数

作者：知新_RL | 2024-02-10 19:32:10

踩

怎么求素数

 
  转载自：  http://blog.csdn.net/si_ji_feng/article/details/8555325 
 
 
  
 
 
 
  
 
 
 (一)      一般求素数方法（对某些OJ 来说会超时）    
 /*求素数的三种方法    
 一：for(i=2;i<=(n-1);i++)    
 if（n%i＝＝0）i 在2 到n-1 之间任取一个数,如果n 能被整除则不是素数，否则就是素数    
 二：for(i=2;i<n/2;i++)    
 if(n%i==0) /*i 在2 到n/2 之间任取一个数,如果n 能被整除则不是素数，否则就是素数    
     
 三：for(i=2;i<(n=sqrt(n));i++)    
 if(n%i==0) /*i 在2 到sqrt(n)之间任取一个数,如果n 能被整除则不是素数，否则就是素数,   
 在下省了下面的输出步骤*/      
 (二)    筛法求素数    
     筛法，是求不超过自然数N（N＞1）的所有质数的一种方法。据说是古希腊的埃拉托   
 斯特尼（Eratosthenes，约公元前274—194 年）发明的，又称埃拉托斯特尼筛子。    
        具体做法是：先把N 个自然数按次序排列起来。1 不是质数，也不是合数，要划去。第   
 二个数2 是质数留下来，而把2 后面所有能被2 整除的数都划去。2 后面第一个没划去的数   
 是3，把3 留下，再把3 后面所有能被3 整除的数都划去。3 后面第一个没划去的数是5，   
 把5 留下，再把5 后面所有能被5 整除的数都划去。这样一直做下去，就会把不超过N 的   
 全部合数都筛掉，留下的就是不超过N 的全部质数。因为希腊人是把数写在涂蜡的板上，   
 每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，   
 所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。（另一种解释是当时的   
 数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就   
 像一个筛子。）    
 1.开一个大的bool 型数组prime[]，大小就是n+1 就可以了.先把所有的下标为奇数的标为true,   
 下标为偶数的标为false.    
 2.然后：    
         for( i=3; i<=sqrt(n); i+=2 )    
         {    if(prime)    
               for( j=i+i; j<=n; j+=i )      
 prime[j]=false;    
         }    
 3.    最后输出bool 数组中的值为true 的单元的下标，就是所求的n 以内的素数了。    
       原理很简单，就是当i 是质(素)数的时候，i 的所有的倍数必然是合数。如果i 已经被判   
 断不是质数了，那么再找到i 后面的质数来把这个质    
 数的倍数筛掉。    
       一个简单的筛素数的过程：n=30。    
       1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30    
       第  1  步过后2 4 ... 28 30 这15 个单元被标成false,其余为true。    
       第  2  步开始：    
       i=3;  由于prime[3]=true,  把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]标为false.    
       i=4;  由于prime[4]=false,不在继续筛法步骤。    
       i=5;  由于prime[5]=true,  把prime[10],[15],[20],[25],[30]标为false.    
       i=6>sqrt(30)算法结束。    
       第  3  步把prime[]值为true 的下标输出来：    
       for(i=2; i<=30; i++)    

[plain]view plaincopy 
   
       if(prime) printf("%d ",i);    
       结果是  2 3 5 7 11 13 17 19 23 29    
       这就是最简单的素数筛选法，对于前面提到的10000000 内的素数，用这个筛选法可以大   
 大的降低时间复杂度。把一个只见黑屏的算法    
 优化到立竿见影，一下就得到结果。关于这个算法的时间复杂度，我不会描述，没看到过类   
 似的记载。只知道算法书上如是说：前几年比    
 较好的算法的复杂度为 o(n),空间复杂度为 o(n^(1/2)/logn).另外还有时间复杂度为 o(n/logn),   
 但空间复杂度为O(n/(lognloglogn))的算法。    
 我水平有限啦，自己分析不来。最有说服力的就是自己上机试一试。下面给出这两个算法的   
 程序：    
 //用了筛法的方法：    
 #include<stdio.h>    
 #include<math.h>    
 #define N 10000001    
 bool prime[N];    
 int main()    
 {    
       int i, j;    
       for(i=2; i<N; i++)    
       {    
             if(i%2==0)//偶数      
             {    
                   prime[i]=false;    
             }    
             else//奇数    
             {    
                   prime[i]=true;    
             }    
       }    
       for(i=3; i<=sqrt(N); i+=2)    
       {          
             if(prime[i])//奇数    
             {    
                   for(j=i+i;j<N;j+=i)//奇数的倍数    
                   {    
                          prime[j]=false;    
                   }    
             }    
       }    
       for(i=2;i<100;i++)//由于输出将占用太多io 时间，所以只输出2-100 内的素数。可以把100   
 改为N    
       {    
             if(prime[i])    
             {    

[plain]view plaincopy 
   
               printf("%d ",i);    
           }    
       }    
       printf("\n");    
       return 0;    
 }    
 (三)    
 算法，这是一种利用了概率和费马小定理的算法设计，有点玄乎吧，其实本人也是刚    
 接触这种算法，这是一种纯数学的解法，如果各位不懂，当学习一下数学也好啊    
 好，我们往下讲    
 首先了解基本的数学知识，费马小定理：    
 若n 是素数，则对所有1≤a≤n-1 的整数a，有a^(n-1)mod n=1;    
 作者Fermat  很牛的数学家，在他在世的时候好像还没有计算机，不过今天我们要用    
 这个定理来设计算法    
 分析这个定理可以知道，如果一个数是质数，那么它必定满足任意一个整数属于(1，n-1)    
 范围有a^(n-1)mod n=1，不懂？我们取逆否命题试试看，就是只要存在在(1，n-1)范围中    
 的整数a  使得a^(n-1)mod  n=1 不成立，那么这个数就不是素数，相信明白了吧，我们要确   
 定    
 一个数是否是素数，只要随机生成一系列的数a，如果这些数a 使N 满足费马小定理的话    
 那么就可以认定它是素数了，当然有个前提，就是这个推导只能在计算机领域内使用    
 就跟我上次讲的用哥德巴赫猜想优化一道算法题目一样，在计算机可以运算的数的范围    
 内可用，请不要在其他科学领域类使用    
 /*    
   
 *费马小定理的应用，求质数    
 *Miller-Rabin 算法    
 *2008 12 27    
 */    
 #include"stdio.h"    
 #include"stdlib.h"    
 #include"math.h"    
 #include"time.h"    
      
 int Btest(int a,int n)    
 {    
  int s = 0;    
  int t = n-1;    
  int i , j , k;    
  int x = 1;    
  int y;    
  i = 1;    
  do{    
   s++;    
   t = t / 2;    
  }while((t%2)!=1);  

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/75287