转自我的博客，原文链接：http://blog.amaok.com/2018/prime_linear_sieve

突然更新的学习笔记。

最近做了一道在很大的范围里筛选出素数的神仙题，因为超时搞得很头疼，所以想来深入了解一下线性筛法，提高程序运行效率。

我们常说的线性筛是指在线性时间内把素数表筛出来的过程，这里介绍两种筛法.

一般筛法（埃拉托斯特尼筛法）：

基本思想：素数的倍数一定不是素数

实现方法：用一个长度为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

 

下面我们来介绍一波真正的线性筛（欧拉筛法）：

我们发现在上面的筛法中有的数字是多个素数的倍数，也就是说它可能会被重复计算多次，比如说6同时是2与3的倍数，它在计算时就被访问了两次,这样会导致效率低下，所以在下面的算法中我们考虑如何优化这种情况。

原理：

任何一个合数都可以表示成一个质数和一个数的乘积

假设A是一个合数，且A = x * y，这里x也是一个合数，那么有:

A = x * y; (假设y是质数，x合数)

x = a * b; (假设a是质数，且a < x——>>a<y) -> A = a b y = a Z (Z = b y)

即一个合数(x)与一个质数(y)的乘积可以表示成一个更大的合数(Z)与一个更小的质数(a)的乘积，那样我们到每一个数，都处理一次，这样处理的次数是很少的，因此可以在线性时间内得到解。

仍然按上面的例子模拟（这里0为是素数，1为非素数，p为记录的素数表）：

初始：

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

p(empty)

然后到2的位置，把2放入素数表,做当前范围内可以筛掉的处理（具体是怎样的看代码叭）：

1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

p 2 到3，把3放入素数表，继续处理

1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0

p 2 3 然后到了4，它不是个素数，也处理一下

1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0

p 2 3 .......

然后一直搞下去，最后也能得到完整的素数表，这样虽然看起来复杂一些，但是实际上我们发现对于每个数的处理几乎是O(1)的。

1  void get_list(){2        for(int i=2;i<=maxn;i++){3              if(!is_not_pr[i]) prime[++tot]=i;4              for(int j=1;j<=tot&&i*prime[j]<=maxn;j++){5                    is_not_pr[i*prime[j]]=1;//合数标为1，同时，prime[j]是合数i*prime[j]的最小素因子6                    if(i%prime[j]==0) break;//即比一个合数大的质数和该合数的乘积可用一个更大的合数和比其小的质数相乘得到7              }8        }9 }

 

所以说有了这两个东西后a掉那道题就很轻松了_(:зゝ∠)_