素性筛选

介绍

通过实时判断或预处理，筛选出素数的方法。

暴力试除法

不断除以比自己小的数，若不能被整除则为素数

步骤

• 从 $2$ 开始除，直到 $\sqrt{n}$
• 若 $n$ 能被 $i$ 整除，则 $n$ 不是素数

复杂度

• 时间复杂度 $O(\sqrt{n})$
• 空间复杂度 $O(1)$

代码

bool is_prime(int n) {
    // 0、1不是素数
    if (n <= 1) return false;
    // 从2试到sqrt(n)
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    // 全都不能整除，是素数
    return true;
}

埃拉托斯特尼筛法

维护一个素数标记列，将素数的所有倍数筛掉

设素数集 $\mathbb{P}$

• $p = \{ p_i | p_i \in \mathbb{P}, p_i \leq n\}$（所有素数）
• $t = \{ t_i | t_i \in \mathbb{N^*}, t_i \leq n\}$（所有倍数）

步骤

双层循环

• 筛选掉所有 $p \times t$
• 外层遍历 $p$，内层遍历 $t$
• 被外层筛掉的 $p$ 不会被纳入内层遍历

代码

// 素数集
vector<int> prime; 
// 素数标记列
vector<bool> is_prime;
void filter(int n){
    // 全部设为素数
    is_prime.resize(n, true);
    // 0、1不是素数
    is_prime[0] = is_prime[1] = false;
    // 遍历所有数
    for(int p = 2;p < n;p++){
        // 当前是素数
        if(is_prime[p]){
            // 记录素数
            prime.emplace_back(p);
            // 筛掉倍数
            for(int t = 2;t * p < n;t++)
                is_prime[t * p] = false;
        }
    }
}

欧拉筛法（线性筛）

维护一素数列，将素数列中的每个素数的每个倍数筛掉

设素数集 $\mathbb{P}$

• $p = \{p_i | p_i \in \mathbb{P}, p_i \leq n\}$（所有素数）
• $t = \{t_i | t_i \in \mathbb{N^*}, t_i \leq n\}$（所有倍数）

步骤

• 筛选掉所有 $p \times t$

问题

有些数被筛选两次

举例

• $p = \{2,3,5,7,11,...\}$
• $t = \{1,2,3,4,5,...\}$
  • $p_1 \times t = 2 \times \{1,2,3,4,5,...\} \\= \{2,4,6,8,10,...\}$
  • $p_3 \times t = 5 \times \{1,2,3,4,5,...\} \\= \{5,10,15,20,25,...\}$

10出现了两次！

这是因为：

• $p_1 = t_2 = 2$
• $p_3 = t_5 = 5$
• $p_1 \times t_5 = 2 \times 5 = 10$
• $p_3 \times t_2 = 5 \times 2 = 10$

• 当存在 $a,b,c,d\space (a<c,b<d)$
• 满足 $p_a = t_b, p_c = t_d$ 时，
• 会导致 $p_a \times t_d = p_c \times t_b$，
• 该数被筛掉两次

循环逻辑

• 外层遍历 $t$，内层遍历 $p$，外层边遍历边添加素数
  • 遍历到 $t_b$ 时，$p_c$ 还没有被添加到 $p$ 数列，$t_b \times p_c$ 不起作用
  • 遍历到 $t_d$ 时，$p_a$ 已经被添加到 $p$ 数列，$t_d \times p_a$ 起作用
• 只筛选一次

跳出时机

• $i \times p_j \gt n$ 时，跳出循环

要筛掉的数超过了搜索范围

• $i\space \%\space p_j = 0$ 时，跳出循环

$p_j$ 是 $i$ 的因数，

• 设$i = p_j \times m$，取 $p_k\space (k\gt j)$
• $p_k \times i = p_k \times (p_j \times m) = p_j \times (p_k \times m)$，
• 该数已经被 $p_j$ 筛掉了，不需要再被 $p_k$ 筛选

代码

// 素数集
vector<int> prime; 
// 素数标记列
vector<bool> is_prime;
void filter(int n){
    // 全部设为素数
    is_prime.resize(n, true);
    // 遍历所有倍数t
    for(int t = 2;t < n;t++){
        // 记录素数
        if(is_prime[t]) prime.emplace_back(t);
        // 遍历所有素数p
        for(int p: prime){
            // 越界跳出循环
            if(t * p > n) break;
            is_prime[i * p] = false;
            // 已被筛掉跳出循环
            // 这时候正好p是最小质因子
            if(t % p == 0) break;
        }
    }
}