【算法篇-数论】线性筛法（欧拉筛法）筛 n 以内的质数

本文参考自 B站董晓算法

1.线性筛法（欧拉筛法）介绍

我们的目标是筛出 2 ~ n 以内的质数 最最最暴力的方法就是一个数一个数判断是不是质数 但是这样的时间复杂度是非常高的 而我们本文的欧拉筛法可以做到时间复杂度仅为O(N)

主要的思想就是一个质数的倍数(倍数为1除外)肯定是合数，那么我们利用这个质数算出合数，然后划掉这个合数，下次就可以不用判断它是不是质数，节省了大量的时间。
其实合数的倍数也是合数，这点也可以利用，划去其他的合数

其实这种思想也有一种算法叫埃式筛法，但是埃式筛法会重复地划掉一些合数，相比于欧拉筛法，并不是那么好，所以我们本文只介绍欧拉筛法，感兴趣的小伙伴可以去了解一下埃式筛法。

2.欧拉筛法代码以及分析

const int N = 1000010;
bool v[N]; //记录是不是合数，全局变量默认false
int pri[N],cnt; //pri[i]表示存放的质数，cnt记录质数个数,全局变量默认是0
void get_pri(int n) //参数是求 n 以内的质数
{
  for(int i = 2; i <= n;i++) //从 2 开始筛
  {
      if(!v[i]) //如果没有被划掉(表示不是合数)就说明当前i是质数
      {
          pri[++cnt] = i;//从pri[1]开始存放，所以是++cnt,cnt开始是0
      }
      for(int j = 1; i * pri[j] <= n;j++)//开始枚举已记录的质数，利用这些质数划掉合数 
      {   //for循环里面，i * pri[j] <= n，首先要保证划掉的合数不能大于n，不然没意义
          v[i * pri[j]] = true;//划掉合数
          if(i % pri[j] == 0)//这段代码是精髓
          {
              break;
              //如果i是质数，则最多枚举到自身中断
              //如果i是合数，则最多枚举到自身的最小质数中断
          }
      }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

我们来模拟一下

const int N = 1000010;
bool v[N]; 
int pri[N],cnt; 
void get_pri(int n) 
{
  for(int i = 2; i <= n;i++) 
  {
      if(!v[i]) 
      {
          pri[++cnt] = i;
      }
      for(int j = 1; i * pri[j] <= n;j++) 
      {  
          v[i * pri[j]] = true;
          if(i % pri[j] == 0)
          {
              break;
          }
      }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

求30以内的质数

i = 2时，2不是合数，所以进入if ，pri[1] = 2。
然后开始准备划掉合数，最下面的for循环判断条件 2 * pri[1] = 2 * 2 = 4 <= 30,进入循环
v[2 * pri[1]] = v[2 * 2] = v[4] = true,所以4这个数被我们划掉了，下次不会判断它了。
然后 if(2 % pri[1] == 0) ,就是if(2 % 2 == 0),直接break,
满足i是质数，则最多枚举到自身中断。
1
2
3
4
5

接下来我们直接跳到 i = 4 是，4是合数
1

const int N = 1000010;
bool v[N]; 
int pri[N],cnt; 
void get_pri(int n) 
{
  for(int i = 2; i <= n;i++) 
  {
      if(!v[i]) 
      {
          pri[++cnt] = i;
      }
      for(int j = 1; i * pri[j] <= n;j++) 
      {  
          v[i * pri[j]] = true;
          if(i % pri[j] == 0)
          {
              break;
          }
      }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

i = 4 时，v[4] 上面被我们划掉了，不进入所以不加入到 pri数组里面去
然后开始准备划掉合数
for循环里面 4 * pri[1] == 8 < 30 ，满足条件进入循环
v[4 * 2] = v[8] = true,划掉8这个数
if(4 % pri[1] == 0),也就是if(4 % 2 == 0)满足条件，直接break
满足i是合数时，最多枚举到自身最小的质因子中断。
1
2
3
4
5
6

剩下的大家可以自行代入上面的数值模拟一下。

3.总结

欧拉筛法

 if(i % pri[j] == 0)
{
 		break;
}
1
2
3
4

这段代码是精髓，每次划掉合数时，选择恰当的时机及时中断，避免了后面重复划掉合数，大大提高了算法的效率。
当 i 是质数，而pri[j]里面都是质数，i 只有枚举到自己才能整除等于0，才能中断，也就是i是质数时，最多枚举到自身才中断。
当i 是合数，i最多枚举到自身最小的质因子就中断