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

在做题的过程中，我们会遇到一些需要求素数的要求，如果对于数据范围很小的数据，我们有最简单但是最耗时间的双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

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

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