突然更新的学习笔记。
最近做了一道在很大的范围里筛选出素数的神仙题，因为超时搞得很头疼，所以想来深入了解一下线性筛法，提高程序运行效率。
我们常说的线性筛是指在线性时间内把素数表筛出来的过程，这里介绍两种筛法.
一般筛法（埃拉托斯特尼筛法）：
基本思想：素数的倍数一定不是素数
实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。
说明：整数1特殊处理即可。
举个例子
我们筛前20个数
首先初始为（0代表不是素数，1代表是素数）
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
然后从2开始我们发现2被标记为素数，我们把2的倍数全部筛掉
变为：
0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
接着到3我们发现3仍然被标记，把3的倍数全部筛掉
变为：
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
接着一直重复下去就得到了最后的素数表：
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
2 3 5 7 11 13 17 19
1 const int MAXN = 1000000； 2 void get_list() 3 { 4 int i, j; 5 for (i=0; i<MAXN; i++) prime[i] = 1; 6 prime[0] = prime[1] = 0; 7 for (i=2; i<MAXN; i++) 8 { 9 if (!prime[i]) continue; 10 for (j=i*2; j<MAXN; j+=i) prime[ j ] = 0; 11 } 12 }//调和级数证明可得复杂度为（nlglgn）,所以不能称之为线性筛，但是它的实际运行速度也不是特别慢