GESP五级｜埃氏筛 & 线性筛（欧拉筛）零基础竞赛教程

说明

本节属于 GESP C++五级考点，信奥入门高频数论工具。 作用：一次性找出 1 ~ n 里面所有质数（素数）。

名词解释 质数（素数）：大于1，只能被1和自己整除，例如 2、3、5、7 合数：大于1，不是质数，例如4、6、8、9

统一规则 布尔数组 is_prime[x] is_prime[x] = true → x是质数 is_prime[x] = false → x是合数

前置知识：暴力判断质数（只适合少量数字）

如果只判断一两个数字能不能用，数字很多的时候速度很慢，不适合批量查找。

#include <iostream>
using namespace std;

// 判断一个数x是不是质数
bool checkPrime(int x)
{
    if (x < 2)
        return false;  // 0、1一定不是质数
    // 只需要循环到根号x，节约时间
    for (int i = 2; 1LL * i * i <= x; i++)
    {
        if (x % i == 0) // 能整除，说明有别的因数
            return false;
    }
    return true;
}

int main()
{
    int n;
    cin >> n;
    if (checkPrime(n))
        cout << "质数";
    else
        cout << "合数";
    return 0;
}

一、埃氏筛法（埃拉托斯特尼筛法）

通俗原理

1. 先假设所有数字都是质数
2. 找到一个质数，把它所有倍数全部标记成合数
3. 循环结束，没有被标记的数字就是质数

缺点：同一个合数会被多次标记，数据很大时速度变慢 时间复杂度：$O(n\log\log n)$

带详细注释完整代码

#include <iostream>
#include <cstring> // memset头文件
using namespace std;

const int MAXN = 1000005; // 筛选最大范围，可以根据题目修改
bool is_prime[MAXN];      // 质数标记数组

// 埃氏筛：预处理1~n所有数字的质数标记
void sieve(int n)
{
    // 先把全部数字初始化为true，默认都是质数
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = false;
    is_prime[1] = false; // 0和1不是质数

    // 从2开始遍历每个数字
    for (int i = 2; i <= n; i++)
    {
        if (is_prime[i]) // 如果i是质数
        {
            // 把i的2倍、3倍、4倍……全部标记为合数
            for (int j = i * 2; j <= n; j += i)
            {
                is_prime[j] = false;
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;
    sieve(n); // 执行筛法

    // 输出2~n所有质数
    for (int i = 2; i <= n; i++)
    {
        if (is_prime[i])
            cout << i << " ";
    }
    return 0;
}

考场小贴士

可以优化内层循环起点 j = i * i，但是新手直接写 i*2，不容易写错。

二、线性筛（欧拉筛，五级重难点）

通俗原理

埃氏筛会重复标记合数。 线性筛做到：每一个合数只会被标记一次，速度更快。 时间复杂度：严格 $O(n)$。

核心秘诀：

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

含义：当i能整除这个质数，立刻停止循环，防止重复标记。不能删除！

需要两个数组：

1. is_prime[]：标记是否是质数
2. prime[]：存放找到的所有质数

带详细注释完整代码

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

const int MAXN = 1000005;
bool is_prime[MAXN];  // 标记是否为质数
int prime[MAXN];      // 保存找到的所有质数
int cnt;              // 记录质数一共有多少个

// 线性筛（欧拉筛）
void euler_sieve(int n)
{
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = false;
    is_prime[1] = false;
    cnt = 0; // 质数数量初始化为0

    for (int i = 2; i <= n; i++)
    {
        // 如果i没有被标记，说明i是质数
        if (is_prime[i])
        {
            prime[cnt++] = i; // 存入质数数组
        }

        // 依次取出已找到的质数，用来筛数
        for (int j = 0; j < cnt && i * prime[j] <= n; j++)
        {
            is_prime[i * prime[j]] = false; // 标记为合数

            // 核心关键语句，不可省略
            if (i % prime[j] == 0)
            {
                break;
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;
    euler_sieve(n);

    // 打印所有质数
    for (int i = 0; i < cnt; i++)
    {
        cout << prime[i] << " ";
    }
    return 0;
}

三、两种筛法对比（选择题常考）

1. 埃氏筛 ✅ 优点：代码短，好理解，新手容易写对 ❌ 缺点：合数重复标记，超大范围速度一般 适用：1e5以内数据

2. 线性筛（欧拉筛） ✅ 优点：速度最快，合数只标记一次 ❌ 缺点：代码稍复杂，必须记住break 适用：1e6大数据、GESP五级编程大题

四、零基础考场避坑清单

1. 数组尽量写在全局，防止空间不足程序崩溃
2. 千万不要忘记：is_prime[0]=is_prime[1]=false
3. 线性筛的break不能删掉，删掉直接变成低效筛法
4. 筛法只运行一次，放在循环外面预处理，不要反复调用
5. 相乘容易溢出，范围很大时注意使用long long判断

五、常见考题用法

1. 输出1~n全部质数
2. 统计一段区间内质数总个数
3. 搭配线性筛实现质因数分解（GESP五级拓展大题）

GESP五级/信奥专用 埃氏筛法 & 线性筛（欧拉筛）竞赛教程

前言（考纲定位）

埃氏筛、线性筛属于GESP C++五级官方考点，数论核心算法，同时是CSP-J入门组高频工具。 作用：批量预处理 1~n 所有素数，快速查询、统计素数、分解质因数。 术语约定： 素数（质数）：大于1，只能被1和自身整除； 合数：大于1且不是素数； 数组约定：is_prime[x]=true 代表x是素数，false代表合数。

前置：暴力试除法（单次判素，不适合批量）

适合少量数字单独判断，大规模批量求素数效率极低。

#include <iostream>
using namespace std;

// 判断x是否为素数
bool isPrime(int x)
{
    if(x < 2) return false;        // 0、1不是素数
    // 只需枚举到sqrt(x)
    for(int i = 2; 1LL * i * i <= x; i++)
    {
        if(x % i == 0)
            return false;
    }
    return true;
}

int main()
{
    int x;
    cin >> x;
    if(isPrime(x)) cout << "是素数";
    else cout << "不是素数";
    return 0;
}

一、埃氏筛法（埃拉托斯特尼筛法）

原理

预先默认所有数都是素数；找到素数i，把i所有倍数标记为合数。 复杂度：$O(n\log\log n)$ 缺点：同一个合数会被多个质因子重复标记

带注释满分模板

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

const int MAXN = 1000005;    // 筛的上限，根据题目调整
bool is_prime[MAXN];         // 素数标记数组

// 埃氏筛：预处理1~n素数
void sieve(int n)
{
    memset(is_prime, true, sizeof(is_prime)); // 初始全部标记为素数
    is_prime[0] = is_prime[1] = false;        // 0和1不是素数
    
    for(int i = 2; i <= n; i++)
    {
        if(is_prime[i])    // 如果i是素数
        {
            // 标记i的所有倍数为合数，从i*2开始
            for(int j = i * 2; j <= n; j += i)
            {
                is_prime[j] = false;
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;
    sieve(n);
    // 输出2~n所有素数
    for(int i = 2; i <= n; i++)
    {
        if(is_prime[i])
            cout << i << " ";
    }
    return 0;
}

可选优化：内层循环改为 j = i*i；新手考场推荐直接写i*2，避免边界错误。

二、线性筛法（欧拉筛，五级重难点）

核心思想

保证每个合数只被它最小质因数筛一次，无重复标记，严格线性复杂度 $O(n)$。 必备关键语句：if(i % prime[j] == 0) break; 作用：一旦i能被prime[j]整除，prime[j]是i最小质因子，终止内层循环，杜绝重复筛数。

带注释满分模板

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

const int MAXN = 1000005;
bool is_prime[MAXN];  // 标记数组：是否为素数
int prime[MAXN];      // 存放筛选出来的所有素数
int cnt;              // 记录素数数量

// 线性筛（欧拉筛）
void euler_sieve(int n)
{
    memset(is_prime, true, sizeof(is_prime));
    is_prime[0] = is_prime[1] = false;
    cnt = 0;  // 初始化素数个数为0
    
    for(int i = 2; i <= n; i++)
    {
        if(is_prime[i])
        {
            prime[cnt++] = i;  // i是素数，存入素数数组
        }
        // 枚举已找到的素数，筛 i * prime[j]
        for(int j = 0; j < cnt && i * prime[j] <= n; j++)
        {
            is_prime[i * prime[j]] = false;  // 标记合数
            // 核心断点，不可删除
            if(i % prime[j] == 0)
                break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    euler_sieve(n);
    // 依次输出所有素数
    for(int i = 0; i < cnt; i++)
    {
        cout << prime[i] << " ";
    }
    return 0;
}

三、两种筛法对比（选择题高频考点）

四、GESP五级考场避坑清单

1. 数组开大小时预估数据范围，数组开在全局区避免栈溢出；
2. 不要忘记设置 is_prime[0]=is_prime[1]=false；
3. 线性筛break不能删掉，删掉直接退化成低效埃氏筛；
4. 乘法i*prime[j]存在溢出风险，超int范围改用long long判断；
5. 筛法预处理只运行一次，放在输入前执行，不要重复调用。

五、常见拓展用途（真题常考）

1. 统计区间素数个数；
2. 快速分解数字质因数（欧拉筛预处理最小质因子）；
3. 判断多个数字是否为素数；
4. 求解欧拉函数（线性筛拓展）。

GESP/信奥专用模板（数组版，不使用vector，兼容老旧编译器）

竞赛考场常用，MAXN直接开全局数组（全局区内存更大，不会栈溢出）

1. 埃氏筛（数组标准版·新手首选）

#include <iostream>
using namespace std;

// 全局数组，存放标记；全局变量默认初始值是0(false)
const int MAXN = 1000000;  // 根据题目调整上限
bool is_prime[MAXN + 5];

void Eratosthenes(int n)
{
    // 先全部标记为素数 true
    for (int i = 2; i <= n; i++)
        is_prime[i] = true;

    is_prime[0] = is_prime[1] = false; // 0、1不是素数

    for (int i = 2; i <= n; ++i)
    {
        if (is_prime[i]) // i是素数
        {
            // 从i*2开始标记所有倍数，易懂版本，推荐新手写
            for (int j = i * 2; j <= n; j += i)
            {
                is_prime[j] = false;
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;
    Eratosthenes(n);

    // 输出2~n所有素数
    for (int i = 2; i <= n; ++i)
    {
        if (is_prime[i])
            cout << i << " ";
    }
    return 0;
}

2. 线性筛（欧拉筛·数组标准竞赛模板）

附带素数存储数组，可直接背，支持大数据

#include <iostream>
using namespace std;

const int MAXN = 1000000;
bool is_prime[MAXN + 5];
int prime[MAXN + 5];  // 保存所有素数
int cnt;              // cnt：素数总个数

void Euler(int n)
{
    cnt = 0;
    // 初始化
    for (int i = 2; i <= n; i++)
        is_prime[i] = true;
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n; i++)
    {
        if (is_prime[i])
        {
            prime[cnt++] = i; // 发现素数，存入数组
        }
        // 遍历已经找到的素数
        for (int j = 0; j < cnt; j++)
        {
            int p = prime[j];
            if (1LL * i * p > n) // 防止int溢出，超出范围退出
                break;
            is_prime[i * p] = false;
            // 核心剪枝，线性筛灵魂
            if (i % p == 0)
                break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    Euler(n);

    // 遍历素数数组输出
    for (int i = 0; i < cnt; i++)
    {
        cout << prime[i] << " ";
    }
    return 0;
}

3. 拓展：带最小质因子minp的线性筛（质因数分解必备）

信奥高频拓展，快速分解大数

#include <iostream>
using namespace std;

const int MAXN = 1000000;
int minp[MAXN + 5]; // minp[x] = x的最小质因子
int prime[MAXN + 5];
int cnt;

void euler_minp(int n)
{
    cnt = 0;
    // minp初始为0
    for (int i = 2; i <= n; i++)
    {
        if (minp[i] == 0)
        {
            minp[i] = i;
            prime[cnt++] = i;
        }
        for (int j = 0; j < cnt; j++)
        {
            int p = prime[j];
            if (1LL * i * p > n) break;
            minp[i * p] = p;
            if (i % p == 0) break;
        }
    }
}

// 利用最小质因子分解x，输出质因数
void factor(int x)
{
    while (x > 1)
    {
        int p = minp[x];
        cout << p << " ";
        while (x % p == 0)
            x /= p;
    }
}

int main()
{
    int n;
    cin >> n;
    euler_minp(n);

    int x;
    cin >> x;
    factor(x);
    return 0;
}

📌 考场书写注意事项

1. 数组开全局！ 如果写在main内部，属于栈内存，MAXN=1e6会直接栈溢出运行报错。
2. 1LL * i * p 不能省略！ i、p都是int，相乘容易溢出，先转为long long判断边界。
3. MAXN按需修改：

• GESP四级题目大多 MAXN ≤ 1e6
• NOIP题目常会开到 1e7（注意内存，1e7的bool数组约10MB）

✅ 做题选择建议

• GESP3/4级、数据≤5e5：写【埃氏筛】，代码短、不容易写错
• 大数据、需要质因数分解、数论题目：直接写【线性筛】