当前位置:   article > 正文

素数快速求法 -- 筛法求素数

筛法求素数

在做题的过程中,我们会遇到一些需要求素数的要求,如果对于数据范围很小的数据,我们有最简单但是最耗时间的双for循环嵌套法。下面举个例子。

Question : Get the primes from 1 to 100 and print them.

/**
 * 素数求法 基础for循环法
 */
#include <cstdio>
#include <cmath>
using namespace std;
int main( )
{
    int i,j;
    for(i=1;i<=100;i++)
    {
        for(j=i;j<=sqrt(i);j++)
        {
            if(i%j!=0)
        }
      printf("%d\n",i);
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

这样之后就求出来了1 到100的素数,很简单但是很耗时间啊 一般不用。
好,下面介绍第二种求素数的方法 ——— 筛法求素数

/**
 * 一般线性筛法素数  
 */
    void make_prime()  {        
        memset(prime, 1, sizeof(prime));    //先假设每一个数字为素数 用prime数组标记为1
        prime[0]=false; //注意0 和 1 不是素数      
        prime[1]=false;       
        int N= 31700; //假设数据范围是30000左右       
        for (int i=2; i<N; i++)           
          if (prime[i]) 
          {            
            primes[++cnt]=i;       
            for (int k=i*i;k<N;k+=i)  //筛法的主要实现代码        
                prime[k]=false;         
          }        
        return;  
    }     
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

解释
筛法求素数的思想主要是先将数字假设为素数。用prime标记数组来标记为1表示这个数是素数。但是要注意prime[0] 和 prime[1] 不用假设为素数。 然后就是从2开始。只要prime数组不是0,就执行for循环的遍历,然后将当前的数字k乘以本身,然后更新prime数组为false。然后k = k + i;
这里用到素数一个性质 :一个素数每次乘以2得到的数字就是合数(合数的意思是除了1和本身之外还可以被其他数字整除,和素数相反。)
我们可以在for循环里面用 看= i*2 这个条件的 但是仔细观察用i*i更快一点。这点自己可以在纸上画一画就了解了,说的话很容易晕,在纸上画一画很容易理解的。
这样,我们就用筛法将合数都标记为false了。然后将标记是素数的数字输出就可以得到范围里面的素数了。


上面的一般线性筛法求素数以及可以处理素数的问题了,如果第二种看的不太懂的话,建议先不要看优化的快速筛法求素数。容易乱。其实这样就是当模板用的。找个题目用一下就会了。


优化:快速筛法求素数
其实我们可以发现,在一般的线性的筛法中,我们对范围内的数字筛了很多次,造成了时间的浪费,那么我们可不可以优化呢?当然是可以的。

/**
  * 快速筛法求素数 不考虑偶数 范围直接减半
  */
    half=size/2; //数据规模为size 
int sn = (int) sqrt(size);   
for (i = 0; i < half; i++)   
   p[i] = true;// 初始化全部奇数为素数。p[0]对应3,即p[i]对应2*i+3   
for (i = 0; i < sn; i++) {      
if(p[i])//如果 i+i+3 是素数  
{       
    for(k=i+i+3, j=k*i+k+i; j < half; j+=k)     
    // 筛法起点是 p[i]所对应素数的平方 k^2                                                 
       p[j]=false;   
}   
}   
//素数都存放在 p 数组中,p[i]=true代表 i+i+2 是素数。  
//举例,3是素数,按3*3,3*5,3*7...的次序筛选,因为只保存奇数,所以不用删3*4,3*6....
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

这样的话,我们就可以高效的快速拿下素数了
谢谢大家 第三个代码是我从复制来的 大家有兴趣可以看看这位博主的文章

http://blog.csdn.net/dinosoft/article/details/5829550

好了 素数的问题就说到这里了 我回去整理二分法的算法
拜拜了 各位

有什么不对的地方 欢迎指正 谢谢

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

闽ICP备14008679号