# 求质数的素数筛

# 素数的判定

对于任意自然数 n ，枚举 2 ~ n\sqrt{n} 的所有数，判断能否整除 n （即余数是否为零），若都不能整除，即余数全都不为零，则 n 为质数。

  • 时间复杂度：O (n\sqrt{n})

# 埃拉托色尼筛法（埃氏筛法）

问题：求 2~N 内的所有质数
步骤：

  1. 从 i=2 开始枚举，并将 2~N 范围内 2 的倍数都标记为合数，直到 k*i>N。
  2. i++，然后看 i 是否有在之前的步骤中被标记，若没有被标记，说明 2~i-1 中没有 i 的因素，故 i 为质数。
  3. 优化：不从 i，2*i…… 开始筛，而是从 i*i 开始筛。因为当你扫到 i 的时候，i*2，i*3，……，i*i-1 已经在前面 2，3，……，i-1 的时候被筛掉了，你只需要筛掉 i*i,i*i+1,…… 即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  
void primes(int n)
{
    memset(v,0,sizeof(v));//0表示素数，1表示合数
    for(int i=2;i<=n;i++)
    {
        //若 i 没被标记，则v[i]=0，即 i 是素数，放在prime数组中，并且从 i*i 开始标记所有 i 的倍数
        //若 i 已被标记，则v[i]=1，则 i 的倍数必在之前就被标记过，所以不用进入循环。
        if(!v[i])
        {
            prime[++cnt] = i;//cnt表示素数个数
            for(int j=i*i;j<=n;j+=i)
            {
                v[j] = 1;
            }
        }
    }
}
  • 时间复杂度：O (nlog(logn)nlog(logn))

# 线性筛（欧拉筛）

优化后的埃拉托色尼筛也有重复筛到数的情况，比如 2,3 都会筛 12，2 和 4 都会筛到 24，要保证线性效率，就必须让每个数只被筛一次。

原理：每个数都有唯一一个最小质因子，让每个数只被自己的最小质因数筛去，就可以做到线性时间啦。

思维：如果 i 能整除 prime [j]，则 i*prime [j+1] 肯定能被后面某个数 k*prime [j] 给筛掉，故有以下核心代码：

1
2
  
if(i%prime[j]==0) break;

其意思是，若 i 能整除 prime [j]，则 i*prime [j] 这个数就先不筛，等后面再筛。

换个角度再讲一遍（因为太难理解了，我是笨蛋呜呜呜）

  • 一个合数 n = 其最小质因子 × 其最大非自身因数
  • 我们要让这个 n 在 i 循环到其最大非自身因数的时候被筛掉，其他时间不被筛
  • 首先，先初始化两个数组，isprime [i] 表示 i 是否为素数，取值为 1 表示素数，取值为 0 表示合数，初始先全部赋值为 1。prime [cnt] 存储所有素数，cnt 起到计数的作用。注意，count 不可作为自定义变量名，所以用 cnt 代替吧
  • isprime [1] = 0，因为 1 不是素数。
  • 外层循环 i 从 2 开始循环到 n，先判断 isprime [i] 是否为 1，是的话表示 i 为素数，把 i 加入 prime 数组中。不是的话就不用管啦。
  • 开始最重要的一步：筛数，我们要把 以 i 为最大非自身因数的合数 筛 / 标记为合数，做法就是用 i 去乘以 prime 数组里已有的质数，直到 i % prime [j]==0
  • 为什么呢，因为 prime 里面的质数一定都小于当前的 i，那么此时 i 乘以这些质数得到的合数，就是我们要找的以 i 为最大非自身因数的合数，但是一旦 i % prime [j]==0，这个时候就从数学的角度来写一下吧。
  • 不妨设

k=i∗prime[j]k = i*prime[j]

因为有

i∣prime[j]i | prime[j]

故设

i=prime[j]∗mi = prime[j]*m

即

k=prime[j]∗prime[j]∗mk = prime[j]*prime[j]*m

那么很明显，k 的最大非自身因数不是 i，而是另有其数（不妨设为 p）。所以 k 不能在 i 这一次循环中被筛掉，而是在 i 循环到 p 的时候再被筛掉。

  • 看看前几轮的循环过程吧
i 的值 质数表 筛去的数
2 2 4
3 2，3 6，9
4 2，3 8
5 2，3，5 10，15，25
6 2，3，5 12
7 2，3，5，7 14，21，28，35
…… …… ……
  • 我们可以注意到，12 这个数没有在 i=4 的时候被筛掉，因为 i=4 的时候，首先筛去 4*2=8，然后发现 4 % 2 == 0，故停止筛数了，就不会去筛后面的 4*3=12，那么 12 什么时候筛呢，答案是当 i 循环到 6 的时候，由 6*2=12 筛去。

希望这样能解释清楚了 QwQ

线性筛代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
  
int isprime[1000001];
int prime[100001];
int cnt = 0;

void primes(int n)
{
    memset(isprime, 1, sizeof(isprime));
    isprime[1] = 0;
    for(int i=2; i<=n; i++)
    {
        if(isprime[i])
        {
            prime[++cnt] = i;
        }
        for(int j=1; j<=cnt && i*prime[j]<=n; j++)
        {
            isprime[i*prime[j]] = 0;
            if(i%prime[j]==0)
            {
                break;
            }
        }
    }
    return 0;
}
  • 时间复杂度：O (n)