CC++ & Algorithm

素数筛法——埃氏筛和线性筛，批量“揪出”质数

困难4
语言版本：C++
概述：学习用筛法高效地生成一定范围内的所有质数，埃氏筛简单易懂，线性筛更快更优。

素数筛法——埃氏筛和线性筛，批量“揪出”质数

为什么要学筛法？

质数（也叫素数）是只能被1和它本身整除的大于1的自然数，比如2、3、5、7、11……如果给你一个数字1000，让你找出所有小于等于它的质数，你会怎么做？

最笨的办法是：从2到1000，每个数都用刚才说的试除法——检查它有没有小于它自己的因数。比如判断101是不是质数，就要从2试到10（因为10²=100＜101），如果都除不尽才是质数。这样要重复很多次除法运算，1000个数大约要算几十万次，如果数字更大比如100万，速度就慢得无法忍受。

古代数学家埃拉托斯特尼想出一个巧妙的方法：筛法。它就像用一把筛子把合数（非质数）筛掉，剩下的就是质数。今天我们就来学习两种最常用的筛法：埃氏筛和线性筛。埃氏筛简单好理解，线性筛效率更高，学完它们你就能在1秒内找出100万以内的所有质数。

1. 埃拉托斯特尼筛法（埃氏筛）——把合数“划掉”

核心思想

想象你有一张从2到1000的数字表。从最小的质数2开始，把2的倍数（4、6、8……）全部划掉，因为它们除了1和自身以外还有因数2，所以不是质数。接下来看下一个没被划掉的数3，它是质数，然后把3的倍数（6、9、12……）也划掉。再到5，划掉5的倍数……一直做到什么时候停止呢？只要做到√n（这里√1000≈31.6）就可以了。因为如果一个合数大于√n，它必然有一个小于等于√n的因数，这个因数已经在前面被处理过了。比如合数37×37=1369超过了1000，所以不用管。最后表上剩下的没被划掉的数就是全部质数。

生活中的比喻

班里要选代表，老师要求每个小组按学号顺序站好，从学号2开始说：“所有我的倍数的同学请坐下。”然后学号3说：“所有我的倍数的同学请坐下。”……这样站着的同学就是“质数代表”。注意，学号6会被2和3各叫一次，所以会有重复喊话。

代码实现

#include <iostream>
#include <cstring>   // 为了用memset
using namespace std;

const int N = 1000;          // 要查找的范围

bool isPrime[N + 1];         // isPrime[i] = true 表示i是质数，false表示合数

void sieve() {
    // 初始化：默认所有数都是质数
    memset(isPrime, true, sizeof(isPrime));
    // 0和1不是质数
    isPrime[0] = false;
    isPrime[1] = false;

    // 从2开始到sqrt(N)
    for (int i = 2; i * i <= N; i++) {
        if (isPrime[i]) {        // 如果i是质数
            // 从i*i开始划掉i的倍数，为什么从i*i开始？
            // 因为比i*i小的倍数（如2*i）已经被更小的质数划掉了
            for (int j = i * i; j <= N; j += i) {
                isPrime[j] = false;   // 划掉合数
            }
        }
    }
}

int main() {
    sieve();   // 调用筛法

    cout << "2到" << N << "之间的质数有:" << endl;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;

    return 0;
}

为什么从 i*i 开始划掉倍数？

刚开始学容易写成 j = 2*i，但这样会重复工作。比如当 i=3 时，2×3=6 已经被 i=2 划掉过了；i=5 时，2×5=10、3×5=15、4×5=20 也都被更小的质数划掉了。所以从 i*i 开始，保证每个合数只被它最小的那个质因数第一次处理到。这样能减少不少循环次数。

埃氏筛的不足

埃氏筛虽然高效，但存在一个缺点：同一个合数可能被多次标记。例如合数30，当 i=2 时会被标记一次，当 i=3 时又被标记一次，当 i=5 时还会被标记一次。虽然从 i² 开始减少了重复，但像30这样由多个质因数组成的数仍然会被重复标记。当范围很大时，这种重复标记会浪费大量时间。

2. 线性筛（欧拉筛）——每个合数只标记一次

为了解决埃氏筛重复标记的问题，我们可以用线性筛（也叫欧拉筛）。它的思想是：保证每个合数只被它的最小质因数标记一次，从而让时间复杂度降到 O(N)，也就是和 N 成正比。这意味着处理100万个数只需要大约100万次操作，比埃氏筛更快。

核心步骤

  1. 用一个数组 prime 按顺序记录已经找到的质数。
  2. 从小到大遍历每一个数 i。
  3. 对于每个 i，把它和所有已经找到的质数相乘，得到合数 prime[j] * i，然后标记这个合数为 false。
  4. 关键的一步：当 i % prime[j] == 0 时，停止内层循环。为什么？因为 prime[j] 是 i 的最小质因数，那么 prime[j] * i 的最小质因数也是 prime[j]。如果继续乘更大的质数，得到的合数将会被更大的质因数标记，但该合数应该由它的最小质因数来标记，所以这里要立即停止，避免重复。

生活中类比

想象你在整理班级的体育用品，每个物品上有编号。你有一个小本子记录“最小管理员”。管理员按编号从小到大排队，每个管理员负责一些物品。当物品编号能整除当前管理员时，这个物品就只归他管，后面的管理员不再管这个物品。这样就保证每个物品只有一个管理员标记。

完整线性筛代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1000;                // 范围上限

bool isPrime[N + 1];               // 是否为质数
int prime[N];                      // 存放找到的质数
int primeCount = 0;                // 质数个数计数器

void linearSieve() {
    // 初始化所有数为质数
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = false;
    isPrime[1] = false;

    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            prime[primeCount] = i;      // 记录质数
            primeCount++;
        }
        // 用当前i与已知每个质数相乘，标记合数
        for (int j = 0; j < primeCount && i * prime[j] <= N; j++) {
            int composite = i * prime[j];           // 要标记的合数
            isPrime[composite] = false;             // 标记为合数
            // 关键：如果 i 能被 prime[j] 整除，就停止内层循环
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    linearSieve();

    cout << "2到" << N << "之间的质数有:" << endl;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;

    cout << "共有 " << primeCount << " 个质数。" << endl;
    return 0;
}

为什么 if (i % prime[j] == 0) break; 这么重要？

假设当前 i=4，质数列表有 [2,3]。先让 4×2=8，标记8。此时 4%2==0，立刻 break。如果不 break，就会继续计算 4×3=12 并标记，但 12 的最小质因数是 2，它应该由 i=6 和 prime[0]=2 来标记（6×2=12）。如果我们在这里用 4×3 标记了12，那么当 i=6 时又会再次标记12，造成重复。所以 break 保证了每个合数只被它的最小质因数标记一次。

3. 新手容易犯的错误

错误一：数组开小了

筛法的数组需要 N+1 个元素（因为要包含下标N），很多人写成 bool isPrime[N]，导致访问 isPrime[N] 时越界。建议用 const int N=1000000，然后定义 bool isPrime[N+1]。

错误二：忘记初始化 isPrime[0] 和 isPrime[1]

如果不把0和1设为 false，程序会把它们当成质数输出。初学者常忘。

错误三：埃氏筛循环条件写错

比如 for (int i=2; i<=N; i++) 而不是 i*i<=N，这样会多很多无效判断。或者把内层循环写成 j=2*i，导致重复标记很多。

错误四：线性筛循环时不检查 i * prime[j] <= N

如果质数乘 i 超出了 N，再标记就会数组越界。所以内层循环条件必须包含 i * prime[j] <= N。

错误五：混淆了埃氏筛和线性筛的用途

对于 N ≤ 10^6，埃氏筛已经足够快；对于 N ≥ 10^7，更推荐线性筛。初学者不要盲目追求线性筛，先把埃氏筛用熟。

4. 完整可运行示例（对比两种筛法）

下面给出一个完整的程序，同时使用埃氏筛和线性筛，并统计它们标记合数的次数，让你直观感受效率差异。

#include <iostream>
#include <cstring>
#include <ctime>
using namespace std;

const int N = 1000000;       // 测试100万以内的质数

// 埃氏筛，返回标记次数
int sieveEratosthenes(bool isPrime[]) {
    memset(isPrime, true, (N+1)*sizeof(bool));
    isPrime[0] = false;
    isPrime[1] = false;
    int count = 0;             // 标记次数
    for (int i = 2; i * i <= N; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= N; j += i) {
                if (isPrime[j]) {
                    isPrime[j] = false;
                    count++;
                }
            }
        }
    }
    return count;
}

// 线性筛，返回标记次数
int sieveLinear(bool isPrime[]) {
    memset(isPrime, true, (N+1)*sizeof(bool));
    isPrime[0] = false;
    isPrime[1] = false;
    int prime[N/10];           // 足够大的数组存质数
    int primeCount = 0;
    int count = 0;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            prime[primeCount] = i;
            primeCount++;
        }
        for (int j = 0; j < primeCount && i * prime[j] <= N; j++) {
            isPrime[i * prime[j]] = false;
            count++;
            if (i % prime[j] == 0) break;
        }
    }
    return count;
}

int main() {
    bool isPrime1[N+1], isPrime2[N+1];
    int t1, t2;

    // 测试埃氏筛
    clock_t start = clock();
    int mark1 = sieveEratosthenes(isPrime1);
    clock_t end = clock();
    t1 = double(end - start) / CLOCKS_PER_SEC * 1000;

    // 测试线性筛
    start = clock();
    int mark2 = sieveLinear(isPrime2);
    end = clock();
    t2 = double(end - start) / CLOCKS_PER_SEC * 1000;

    cout << "范围：1 ~ " << N << endl;
    cout << "埃氏筛：标记 " << mark1 << " 次，耗时 " << t1 << " 毫秒" << endl;
    cout << "线性筛：标记 " << mark2 << " 次，耗时 " << t2 << " 毫秒" << endl;
    cout << "两种筛法得到的质数是否相同？" << (memcmp(isPrime1, isPrime2, (N+1)*sizeof(bool))==0 ? "是" : "否") << endl;

    return 0;
}

运行这个程序，你会看到线性筛的标记次数比埃氏筛少很多（大约只有埃氏筛的60%~70%），速度也更快。

5. 更多知识指引

  • 质因数分解：筛出质数后，可以用来快速分解一个数的质因数（比如把30分解成2×3×5）。
  • 区间筛法：如果要求 [L, R] 之间的质数，其中 L 很大但区间长度不大，可以用埃氏筛的思想只筛这个区间。
  • 欧拉函数：线性筛还能用来求1~N每个数的欧拉函数（小于等于该数且与它互质的数的个数），这是数论中重要的函数。
  • Miller-Rabin 素性测试：当要判断一个很大的数（如10^18）是否是质数时，筛法不行了，要用概率算法。

你现在已经掌握了两种常用的筛法，以后遇到需要批量判断质数的题目（比如求1~N的所有质数、验证哥德巴赫猜想等），就可以直接搬出筛法来用了。先练熟埃氏筛，再挑战线性筛，加油！

例题精讲

1单选题

使用埃氏筛（Eratosthenes筛法）求1到n之间的所有质数时，其时间复杂度通常表示为？

AO(n)
BO(n log n)
CO(n log log n)
DO(n^2)
2判断题

在使用埃氏筛标记质数的倍数时，可以从 i*i 开始标记，从而减少不必要的重复标记。

3填空题
以下代码是实现线性筛（欧拉筛）的核心片段，请补全循环体中的判断条件，使得每个合数只被其最小质因子标记一次。

int n;
vector<int> primes;
bool is_prime[100001];
for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) primes.push_back(i);
    for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
        is_prime[i * primes[j]] = false;
        if (___ ) break;
    }
}
4单选题

与埃氏筛相比，线性筛（欧拉筛）的主要优势在于？

A代码更短更易懂
B每个合数只被其最小质因子标记一次，时间复杂度为 O(n)
C不需要额外的布尔数组
D可以只处理奇数，减少一半内存
5填空题
以下埃氏筛代码中，标记质数倍数的循环条件有误，请补全正确的循环条件。

void eratosthenes(int n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = ___; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
}