• C++
  • 埃氏筛 + 线性筛(欧拉筛)C++教程

  • @ 2026-10-21 22:47:25

埃氏筛 + 线性筛(欧拉筛)C++教程

适合:GESP五级 重点:数学道理、优化原因、带详细注释、背诵思路、对比

目标:找出 1 ~ n 里面所有的质数 质数定义:大于1,只能被1和自己整除的整数


前置小知识(先讲数学)

质数:2、3、5、7、11、13…… 合数:4、6、8、9、10、12……(除了1和自己还有别的因数) 1 不是质数,也不是合数!


第一部分:埃氏筛(埃拉托斯特尼筛法)

✅ 数学依据(一定要给学生讲)

思路:

  1. 一开始我们先假设:所有数都是质数
  2. 找到一个质数 p,那么 p 的所有倍数:2p,3p,4p... 一定是合数,全部标记掉
  3. 标记完所有合数,剩下没被标记的,就是质数

举例子 n=10 一开始:[2,3,4,5,6,7,8,9,10]

  • p=2(质数):划掉 4,6,8,10
  • p=3(质数):划掉 6,9
  • p=4:已经被划掉了,跳过
  • p=5:5*2=10 超过范围,不用划 最后剩下 2,3,5,7 就是质数

✅ 优化1:循环到 sqrt(n) 就够了

道理:如果 n 有一个大于 n\sqrt{n} 的因数,那对应的另一个因数一定小于 n\sqrt{n},早就被标记过了。 所以 i 不用跑到 n,跑到 n\sqrt{n} 就可以。

✅ 优化2:从 p*p 开始标记,不用从 2p

比如 p=5: 25=10,10早就被2标记了;35=15早就被3标记了。 比 p² 小的p的倍数,已经被更小的质数标记完了,直接从 p*p 开始筛,减少重复标记。

⚠️ 缺点(埃氏筛致命问题): 一个合数会被多次标记! 比如 12:会被2标记一次、又被3标记一次。重复干活,速度慢。 数字很大的时候,重复标记很多,效率变低。

✅ 埃氏筛完整代码,逐行注释

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

int main()
{
    int n;
    cin >> n;
    // is_prime数组:true代表是质数,false是合数
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false; // 0和1不是质数

    // i从2到根号n
    for (int i = 2; i * i <= n; i++)
    {
        // 如果i还没被标记,说明i是质数
        if (is_prime[i])
        {
            // 从 i*i 开始,把i的倍数标记为合数,步长i
            for (int j = i * i; j <= n; j += i)
            {
                is_prime[j] = false;
            }
        }
    }

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

📖 背诵思路(埃氏筛)

  1. 开布尔数组,初始全true;0、1改成false
  2. i循环:i*i <= n
  3. 如果is_prime[i]是true(i是质数)
  4. j从i*i开始,j每次+i,标记is_prime[j]=false
  5. 最后遍历输出没被标记的

第二部分:线性筛(欧拉筛,线筛)【GESP高频】

✅ 数学依据 + 为什么它更快(重点!)

埃氏筛的毛病:合数重复标记。 线性筛目标:保证 每一个合数,只被它的【最小质因子】标记一次! 每个数字只处理一遍,时间复杂度 (O(n)),所以叫线性筛。

核心规则: 我们维护一个质数数组 prime[],存已经找到的质数。 对于每一个数字 i:

  1. 如果i没被标记 → i是质数,加入prime数组
  2. 遍历已经找到的质数 prime[j]
    • 把 i * prime[j] 标记成合数
    • 如果 i % prime[j] == 0,立刻break!>

    break 这句是线筛灵魂! 道理:prime[j] 是i的最小质因子。如果继续往后乘 prime[j+1] i * prime[j+1] 的最小质因子其实是 prime[j],后面会重复标记,所以直接跳出循环,杜绝重复。

举例子 i=6,prime=[2,3,5] prime[j]=2:6%2==0 → break 不再去乘3、5,防止 6*3=18 被3标记(18最小质因子是2,应该留给i=9,prime[j]=2的时候标记)

✅ 线筛完整代码,逐行详细注释

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

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

    vector<bool> is_prime(n + 1, true); // 标记是否质数
    vector<int> prime;                  // 存放找到的质数

    is_prime[0] = is_prime[1] = false;

    // i遍历2~n所有数
    for (int i = 2; i <= n; i++)
    {
        // 如果i没有被标记,i是质数,放进prime数组
        if (is_prime[i])
        {
            prime.push_back(i);
        }

        // 遍历已经找到的质数
        for (int j = 0; j < prime.size(); j++)
        {
            int p = prime[j];
            int num = i * p;
            if (num > n) break; // 超过范围,不用标记

            is_prime[num] = false;

            // 灵魂判断:i能被p整除,立刻break
            if (i % p == 0)
            {
                break;
            }
        }
    }

    // 输出质数
    cout << "1~" << n << "的质数:";
    for (int x : prime)
    {
        cout << x << " ";
    }
    return 0;
}

📖 背诵思路(线筛,分4句口诀,超好背)

  1. 两个数组:布尔标记is_prime,int数组prime存质数;0、1设false
  2. i从2循环到n;i是质数就push进prime
  3. 循环遍历prime里面的每个质数p
    • 算 num = i * p,超n就break
    • num标记合数
    • 如果 i % p == 0 → break(核心!)
  4. 最后直接输出prime数组

✨ 一句话区分两个筛子 埃氏筛:找质数p,批量划p的倍数;会重复标记,简单好写,慢一点 线筛:保证每个合数只被最小质因子标记一次,没有重复,速度最快,GESP推荐优先写线筛


第三部分:对比总结(板书用)

筛法 时间 优点 缺点 核心
埃氏筛 O(nlog⁡log⁡n)O(n\log\log n) 逻辑简单,代码短,好理解 合数多次重复标记,大数据慢 质数划掉自己所有倍数
线性筛 (O(n))(O(n)) 无重复标记,速度最快 逻辑稍微绕一点,要理解break 每个合数只用最小质因子标记

第四部分:课堂小练习

  1. n=20,用埃氏筛手动模拟一遍,写出标记过程
  2. n=20,线筛,想一想为什么 i=4 的时候遇到 p=2 就要break?

第五部分:给学生的避坑提醒

  1. 数组大小一定要 n+1,因为我们要用到数字n
  2. vector 很省内存,筛大数优先用它
  3. 线筛的break千万不能丢,丢了就退化成普通筛,失去线性的优势
  4. ii 容易溢出!GESP如果n很大,优先用线筛,避免ii溢出问题

2 条评论

  • @ 2026-10-21 22:54:34

    我们慢慢拆开讲,大白话,小学生也能听懂:

    先回顾埃氏筛为什么会重复标记

    拿数字 12 举例: 12 = 2 × 6 12 = 3 × 4

    • 当 i=2(质数)的时候:会把 4、6、8、12、14……全部标成合数
    • 当 i=3(质数)的时候:会把 6、9、12、15……全部标成合数

    👉 12 被标记了两次。 一个合数,只要它有多个质因子,就会被不同质数多次扫到,反复标记。 数字越大,重复次数越多,白白多干活,速度变慢。


    核心思想:规定一条铁规矩

    任何一个合数,只能由它最小的那个质因子负责标记它!

    12 的质因子是 2 和 3,最小质因子是 2。 所以:12 只能交给 2 来标记,不许 3 再来标记 12。 同理: 18 = 2 × 9,最小质因子是 2,只能让2标记18,3不能标记18 15 = 3 × 5,最小质因子是3,只能让3标记15,5不能标记15

    只要守住这条规矩:每个合数只会被标记一次,没有多余操作。

    那代码里 if(i % p == 0) break; 是怎么实现这条规矩的?

    for (int j = 0; j < prime.size(); j++)
    {
        int p = prime[j];
        int num = i * p;
        if (num > n) break;
        is_prime[num] = false;
        if (i % p == 0) break;   // 灵魂一句
    }
    

    prime 数组里面质数是从小到大排的:2,3,5,7,11…… p 从小到大拿出来。

    一旦 i % p == 0: 说明 p 是 i 的最小质因子!

    举例子:i=6,prime=[2,3,5]

    • 第一个 p=2: 6 % 2 == 0 ✔ 立刻 break,不再去拿 p=3、p=5 继续乘。

    为什么不能继续算 6 * 3 = 18? 18 = 6 × 3 但是 18 的最小质因子是 2,不是3! 如果现在用 6 × 3 标记18,就相当于让3去标记本该由2标记的合数,破坏规矩,以后就会出现重复标记。 18 正确标记时机:等 i=9 的时候,p=2,9*2=18,由最小质因子2标记。

    ✅ 一句话: 只要 i 能被 p 整除,p 就是 i 的最小质因子;后面更大的质数乘出来的数,最小质因子还是 p,留给后面处理,现在直接停下。

    为什么做到“每个合数只标记一次”之后,复杂度是 O(n)(线性)

    总共有 2 ~ n,一共 n-1 个数。 每一个合数,刚好被标记 1 次;质数不被标记。 所有标记操作的总次数,不会超过 n。 工作量和 n 成正比,所以叫线性时间 O(n)。

    对比: 埃氏筛:操作次数比 n 多很多,有大量重复,是 O(nlog⁡log⁡n)O(n\log\log n),不是线性。

    简短背诵版(给学生写笔记)

    1. 埃氏筛:同一个合数,会被好几个质数反复标记,重复干活,慢。
    2. 线性筛定下规则:合数只能由它最小的质因子标记,只标记一次。
    3. if(i%p==0) break; 的作用: p 是i的最小质因子,再往后更大质数相乘得到的数,最小质因子还是p,不能现在标记,立刻跳出循环。
    4. 没有多余重复操作,总工作量和n成正比,时间O(n),叫线性筛。

    要不要我拿 i=4、i=6、i=9 一步步手动模拟一遍完整线筛流程?跟着走一遍就彻底通透了。

    手动模拟线性筛(n=20,一步步来)

    初始: is_prime[] 全部先设为true;is_prime[0]=is_prime[1]=false prime = [] (空数组,用来存找到的质数) prime里面永远从小到大:2,3,5,7,11……

    规则再复习:

    1. 如果 is_prime[i]==true → i是质数,放进prime数组
    2. 遍历prime里每一个质数p,算 num = i * p
      • num>20,停止内层循环
      • is_prime[num] = false
      • 如果 i % p == 0 → break内层循环!

    i = 2 is_prime[2]=true → 2是质数,prime变成 [2] 内层循环遍历prime: p=2,num=2*2=4 ≤20 is_prime[4]=false 判断:2%2 ==0 ✅ → break内层循环

    现在标记了:4

    i = 3 is_prime[3]=true → 3是质数,prime变成 [2,3] 内层循环: p=2,num=32=6 ≤20,is_prime[6]=false 判断:3%2≠0,不break,继续 p=3,num=33=9 ≤20,is_prime[9]=false 判断:3%3==0 ✅ → break

    现在标记新增:6、9

    i = 4 is_prime[4]=false,不是质数,不加入prime,prime还是[2,3] 内层循环: p=2,num=42=8 ≤20,is_prime[8]=false 判断:4%2 ==0 ✅ → break!不拿p=3继续算 43=12 👉 重点:12的最小质因子是2,不该在这里用4×3标记,留给后面处理

    新增标记:8

    i = 5 is_prime[5]=true → 5是质数,prime变成[2,3,5] 内层循环: p=2,num=52=10,is_prime[10]=false,5%2≠0 p=3,num=53=15,is_prime[15]=false,5%3≠0 p=5,num=5*5=25 >20 → break

    新增标记:10、15

    i = 6 is_prime[6]=false,不进prime,prime[2,3,5] 内层循环: p=2,num=62=12 ≤20,is_prime[12]=false 判断:6%2 ==0 ✅ → break!不再算63=18 👉 18最小质因子是2,不能现在标记

    新增标记:12

    i = 7 is_prime[7]=true → 7是质数,prime变成[2,3,5,7] 内层循环: p=2 → num=14,标记14,7%2≠0 p=3 → num=21>20,停止内层

    新增标记:14

    i = 8 is_prime[8]=false 内层循环: p=2,num=8*2=16,标记16 8%2==0 → break

    新增标记:16

    i = 9 is_prime[9]=false 内层循环: p=2,num=92=18,标记18 9%2≠0,继续 p=3,num=93=27>20,停止

    ✅ 这里终于标记了18! 18 = 9 × 2,最小质因子是2,符合规矩! 之前i=6的时候不让标记18,就是等这一刻 新增标记:18

    i = 10 is_prime[10]=false 内层循环: p=2,num=10*2=20,标记20 10%2==0 → break

    新增标记:20

    i=11 ~ 20: i=11:质数,加入prime;p=2 → 22>20,内层直接结束,无标记 i=12:合数;p=2 → 24>20,无标记 i=13:质数;p=2→26>20 i=14:合数;p=2→28>20 i=15:合数;p=2→30>20 i=16:合数;p=2→32>20 i=17:质数;p=2→34>20 i=18:合数;p=2→36>20 i=19:质数;p=2→38>20 i=20:合数;p=2→40>20


    ✅ 全部标记过的合数汇总: 4,6,8,9,10,12,14,15,16,18,20 每一个合数,只被标记了一次! 我们检查18:只在i=9,p=2的时候标记,仅此一次。

    ✅ 最后prime数组里面的质数: [2,3,5,7,11,13,17,19]

    提炼这个模拟里面最关键的两处

    1. i=4,p=2,4%2==0,break,不计算4*3=12 12交给i=6,p=2的时候标记(最小质因子2)
    2. i=6,p=2,6%2==0,break,不计算6*3=18 18交给i=9,p=2的时候标记(最小质因子2)

    只要触发i%p==0就break,就是为了守住:合数只能由最小质因子标记

    课堂一句话总结

    只要break写对,没有一个合数会被重复打上标记,总操作次数和n差不多,所以叫线性筛O(n)。

    练习1(课堂手写题)

    题目:n=15,用线性筛手动模拟,按步骤填空 初始: is_prime[0]=is_prime[1]=false,其余初始true;prime = []

    规则复习:

    1. 如果 is_prime[i]==true → i是质数,push_back进prime
    2. 依次取 prime[j]=p,num = i * p
      • num>15,停止内层循环
      • is_prime[num]=false
      • 如果 i % p == 0 → break内层循环!

    请一步步填写: i = 2 is_prime[2] = true → prime = [____] p=2,num=4,标记4为合数;2%2==0 → break 本次标记合数:________

    i = 3 is_prime[3] = true → prime = [,] p=2,num=6,标记6;3%2≠0,继续 p=3,num=9,标记9;3%3==0 → break 本次标记合数:________

    i = 4 is_prime[4]=false p=2,num=8,标记8;4%2==0 → break 本次标记合数:________

    i = 5 is_prime[5]=true → prime = [,,] p=2,num=10,标记10;5%2≠0 p=3,num=15,标记15;5%3≠0 p=5,num=25>15,停止 本次标记合数:______

    i = 6 is_prime[6]=false p=2,num=12,标记12;6%2==0 → break 本次标记合数:________

    i=7:质数,加入prime,p=2 → 14,标记14;7%2≠0,p=3→21>15结束 本次标记合数:14

    i=8~15:i*2全部大于15,不再产生新标记

    👉 问题:

    1. 最后prime里面存放的质数是哪些?
    2. 合数15是在哪一轮、i等于几、p等于几的时候被标记的?
    3. 思考:i=6的时候,为什么break,不能算 6*3=18?

    参考答案(老师版)

    i=2:prime=[2],标记:4 i=3:prime=[2,3],标记:6、9 i=4:prime不变,标记:8 i=5:prime=[2,3,5],标记:10、15 i=6:prime不变,标记:12 i=7:prime=[2,3,5,7],标记:14

    1. 最终质数:2,3,5,7,11,13
    2. 15:i=5,p=3
    3. 18超过n=15,这题里不会出现;核心道理:如果n更大,18最小质因子是2,不能用6×3标记,防止重复标记
    • @ 2026-10-21 22:48:20

      更新后完整试卷(空白学生版)

      筛法专项课堂小测(埃氏筛、线性筛) 满分:40分,课堂20分钟完成

      一、填空题(每空2分,共16分)

      1. 质数定义:大于1,只能被______和______整除的正整数;数字______既不是质数也不是合数。
      2. 埃氏筛的核心思想:找到一个质数p,把p所有的______标记为合数。
      3. 埃氏筛优化:j不从 2*p 开始,而是从 ______ 开始标记,原因是:比这个数小的p的倍数,已经被更小的质数标记过了。
      4. 线性筛(欧拉筛)的目标:每一个合数,只被它的________标记一次,保证没有重复标记。
      5. 线筛里面灵魂一句:if(i % p == 0) break; 如果删掉这句,线筛就退化成普通筛,会出现________标记合数的问题。
      6. 模数n=30,筛的时候数组要开到______,才能存到数字30。

      二、选择题(每题3分,共12分)

      1. 下面哪一个是质数?() A. 9 B. 13 C. 15 D. 21
      2. 埃氏筛 i 的循环条件写成 i*i <= n,主要目的是() A. 代码更好看 B. 减少循环次数,不用循环到n C. 防止输出错误 D. 让程序变成线性时间
      3. 关于埃氏筛和线性筛说法正确的是() A. 埃氏筛时间复杂度O(n) B. 线性筛会多次标记同一个合数 C. 线性筛依靠最小质因子筛数 D. 埃氏筛不能筛100以内质数
      4. 在线性筛中,prime数组作用是() A. 标记数字是不是质数 B. 存放已经找到的质数 C. 存放合数 D. 记录循环次数

      三、读代码简答题(每题4分,共8分)

      1. 模拟埃氏筛:n=12 一开始:0、1标记为false,212默认true i=2,是质数,从4开始标记4,6,8,10,12为合数; i=3,是质数,从9开始标记9、12为合数; i=4:is_prime[4]是false,跳过; 问:112里面最后剩下哪些质数?
      2. 线筛思考题:i=6,质数列表prime={2,3,5} 第一轮p=2,num=62=12,标记12为合数; 然后判断 6 % 2 == 0,触发break,不再拿6去乘3、5。 请问:为什么这里必须break,不能继续算 63=18?

      四、编程题(4分) 编写线性筛(欧拉筛)C++代码,输入n,输出1~n之间全部质数。 要求:使用vector,注释可以简写。


      参考答案版

      一、填空

      1. 1,它本身,1
      2. 倍数
      3. p*p
      4. 最小质因子
      5. 重复
      6. 31

      二、选择 1.B 2.B 3.C 4.B

      三、简答

      1. 2、3、5、7、11
      2. 18的最小质因子是2。如果现在用i=6、p=3标记18,属于重复标记;18应当在后面i=9,p=2的时候,由最小质因子2标记。break用来杜绝重复标记,保证线性。

      四、编程参考代码

      #include <iostream>
      #include <vector>
      using namespace std;
      int main()
      {
          int n;
          cin >> n;
          vector<bool> is_prime(n+1,true);
          vector<int> prime;
          is_prime[0]=is_prime[1]=false;
          for(int i=2;i<=n;i++)
          {
              if(is_prime[i]) prime.push_back(i);
              for(int j=0;j<prime.size();j++)
              {
                  int p=prime[j];
                  int num=i*p;
                  if(num>n) break;
                  is_prime[num]=false;
                  if(i%p==0) break;
              }
          }
          for(int x:prime) cout << x << " ";
          return 0;
      }
      
      • 1