🚀 排行总结（按实际运行速度和复杂度综合）

排名 名称 理论复杂度 实际速度 特点
🥇 1 线性筛（Euler Sieve） O(n) ⚡⚡⚡⚡⚡ 每个合数只标一次，最干净最快
🥈 2 快速埃式（奇数筛/位压缩版） O(n log log n) ⚡⚡⚡⚡ 节省空间、跳偶数
🥉 3 标准埃式筛（Eratosthenes） O(n log log n) ⚡⚡⚡ 简单、稳健，入门首选
🪨 4 试除法（6k±1 或暴力） O(n√n) 🐢 太慢，只适合单个数判素

💬 总结一句人话：

  • 只想快速写完题 → 标准埃式筛。
  • 想搞高效算法 / 竞赛用 → 线性筛。
  • 只判断一个数是不是素数 → 6k±1试除法。
  • 还用暴力除法 → 你在浪费电。

上述就是筛法的一个排行 试除法和暴力除法我们这里不涉及 因为一点意义都没有!!!!!

埃式筛(也就是标准筛)

好，那我用最“人话”的方式教你学会埃式筛。就当我们在教一个刚学会 for 循环的小孩。
我们一步一念，绝对不会跳。

🧠 你要干什么？

找出 1 到 200 里所有的素数。
素数就是——只能被 1 和自己整除的数，比如：2, 3, 5, 7, 11…

🧩 第一步：准备一张表

想象一张表：

1
2
编号： 0  1  2  3  4  5  6  7  8  9  10 ... 200
内容： 否 否 是 是 是 是 是 是 是 是 ...
  • 我们先假设所有数字都是素数，用 1 表示“是素数”，用 0 表示“不是”。
  • 但是我们知道 0 和 1 不是素数，所以把它俩设为 0。

C 语言实现：

1
2
3
4
5
int is_prime[201];
for (int i = 0; i <= 200; i++) {
    is_prime[i] = 1;  // 先都当作是素数
}
is_prime[0] = is_prime[1] = 0;  // 0和1不是素数

🧩 第二步：从 2 开始圈掉倍数

我们从第一个素数 2 开始。
2 的倍数（除了 2 本身）都不是素数，比如 4、6、8、10……
所以我们把这些位置标成 0。

1
2
3
for (int j = 2 * 2; j <= 200; j += 2) {
    is_prime[j] = 0;
}

🧩 第三步：找下一个没被划掉的数

划完 2 的倍数后，表里下一个没被划掉的数是 3。
那 3 就是下一个素数。
再把 3 的倍数（9, 12, 15, 18…）划掉。

1
2
3
for (int j = 3 * 3; j <= 200; j += 3) {
    is_prime[j] = 0;
}

🧩 第四步：重复这个过程

继续往后找：

  • 下一个没被划掉的是 5 → 划掉 25, 30, 35…
  • 再下一个是 7 → 划掉 49, 56, 63…
  • 一直循环，直到 √200 ≈ 14 为止。

完整循环写法：

1
2
3
4
5
6
7
for (int i = 2; i * i <= 200; i++) {
    if (is_prime[i] == 1) {  // 如果这个数还没被划掉
        for (int j = i * i; j <= 200; j += i) {
            is_prime[j] = 0; // 划掉它的倍数
        }
    }
}

🧩 第五步：打印结果

最后，把还没被划掉（值为1）的数都输出，就是所有素数。

1
2
3
4
for (int i = 2; i <= 200; i++) {
    if (is_prime[i] == 1)
        printf("%d ", i);
}

✨ 最终完整代码

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
#include <stdio.h>

int main() {
    int is_prime[201];
    for (int i = 0; i <= 200; i++) {
        is_prime[i] = 1;
    }//给他们带上素数的棋子
    is_prime[0] = is_prime[1] = 0;//这两个不是素数 直接抬走

    for (int i = 2; i * i <= 200/*这里这样写就是可以降低重复率*/; i++) {
        if (is_prime[i] == 1) {//先给那些标称素数的进行一个验证
            for (int j = i * i; j <= 200; j += i) {
                is_prime[j] = 0;
            }
        }
    }

    printf("200以内的素数：\n");
    for (int i = 2; i <= 200; i++) {
        if (is_prime[i] == 1)
            printf("%d ", i);
    }
    printf("\n");
    return 0;
}

🪄 你可以这么理解它：

  • is_prime 就是一堆小旗子。
  • 你从 2 开始，一个一个数过去。
  • 每当遇到一个还竖着的小旗（说明它是素数），
    你就拿着大笔刷去把它的倍数“涂掉”。
  • 最后剩下没被涂掉的，都是素数。

快筛

🧠 先搞清楚：

“快筛”不是新算法，它就是普通埃式筛的小升级：
👉 不去处理所有偶数（因为除了 2，偶数全是合数）。
👉 所以我们只管奇数，少干一半活。

你可以理解成：

原本你要清理 200 个房间，现在只清理奇数号的那 100 个，速度自然翻倍。

🧩 我们来一步步写：

第一步：准备数组

我们只存奇数的状态。
下标 i 代表数字 2*i + 1。
比如：

i 表示的数字
0 1
1 3
2 5
3 7
4 9
… …

C代码里：

1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include <string.h>

int main() {
    const int N = 200;
    int size = (N - 1) / 2 + 1;  // 表示到N的奇数数量
    unsigned char is_prime[size];
    memset(is_prime, 1, sizeof(is_prime)); // 全部假设是素数
    is_prime[0] = 0; // 1 不是素数

第二步：开始筛

我们要从 3 开始（下标 1），只筛奇数。

1
2
3
4
5
6
7
8
9
for (int i = 1; (2*i + 1) * (2*i + 1) <= N; i++) {
    if (is_prime[i]) {
        int p = 2*i + 1; // 还原真实数字
        // 从 p*p 开始划去奇数倍
        for (int j = (p*p - 1)/2; j < size; j += p) {
            is_prime[j] = 0;
        }
    }
}

逻辑解释：

  • 从第一个奇数素数 3 开始；
  • 不用标偶数倍，比如 6、12、18；
  • 只标奇数倍，比如 9、15、21；
  • 所以只动一半的数，速度翻倍。

第三步：输出结果

别忘了 2 是唯一的偶数素数，要单独打印。

1
2
3
4
5
6
7
8
9
    printf("200以内的素数：\n");
    printf("2 ");
    for (int i = 1; i < size; i++) {
        if (is_prime[i])
            printf("%d ", 2*i + 1);
    }
    printf("\n");
    return 0;
}

📜 最终完整代码：

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
#include <stdio.h>
#include <string.h>

int main() {
    const int N = 200;
    int size = (N - 1) / 2 + 1;        // 奇数数量
    unsigned char is_prime[size];
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = 0;                   // 1 不是素数

    for (int i = 1; (2*i + 1) * (2*i + 1) <= N; i++) {
        if (is_prime[i]) {
            int p = 2*i + 1;
            for (int j = (p*p - 1)/2; j < size; j += p)
                is_prime[j] = 0;
        }
    }

    printf("200以内的素数：\n2 ");
    for (int i = 1; i < size; i++) {
        if (is_prime[i])
            printf("%d ", 2*i + 1);
    }
    printf("\n");
    return 0;
}

🎯 傻瓜总结

操作 意思 为什么这样做
只存奇数 少一半空间 偶数没必要筛
从 p*p 开始 前面的倍数早被更小素数划了 省事
每次加 p 跳到下一个奇数倍 不碰偶数
单独打印 2 唯一的偶数素数 特殊待遇

🧮 运行结果：

1
2
200以内的素数：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

一句话记住：

“快筛”就是埃式筛 + 跳偶数。
做的事一样，干得更快。

线性筛

🍎 故事开场：

我们要从 1 数到 20，找出哪些数是素数。
你是“质数班长”，手里拿一支笔，要在黑板上划掉不是素数的数字。

🧩 规则很简单：

  1. 从 2 开始，一个个往上看。
  2. 如果这个数还没被划掉 → 它就是素数。
  3. 然后你拿“你已经认识的所有素数”去乘它。
  4. 每乘出来一个结果，就把那个结果划掉。
  5. 一旦发现这个素数整除了你当前的数字，就停下来，不划更多。

👀 举例说明：

第一个数字：2

  • 没被划掉 → 是素数。
  • 素数表：[2]
  • 拿 2 去乘它自己：2*2=4 → 划掉 4。
  • 因为 2%2==0 → 停。

下一个数字：3

  • 没被划 → 是素数。
  • 素数表：[2, 3]
  • 用 2 去乘：3*2=6 → 划掉 6。
    因为 3%2!=0，继续；
  • 用 3 去乘：3*3=9 → 划掉 9。
    因为 3%3==0，停。

下一个数字：4

  • 4 已经被划掉 → 跳过，不是素数。
  • 但我们也要拿 2 去乘：
    4*2=8 → 划掉。
    因为 4%2==0 → 停。

继续到 5：

  • 没被划 → 是素数。
  • 素数表 [2,3,5]
  • 乘：
    5*2=10 → 划掉
    5*3=15 → 划掉
    5*5=25 超出范围 → 停

6：

  • 已被标 → 合数
  • 拿 2 乘：6*2=12 → 划掉
  • 因为 6%2==0 → 停

就这样一轮一轮下去，每个数字只被“第一个能整除它的质数”划一次。

🧮 结果：

没被划掉的数字 = 素数。
对 1~20 来说：
2, 3, 5, 7, 11, 13, 17, 19

💻 C语言实现（超级傻瓜版）

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
27
28
29
30
#include <stdio.h>
#include <string.h>

int main() {
    const int N = 200;
    int is_comp[N + 1];  // 0 表示还没划掉，1 表示已经划掉
    int primes[N + 1];   // 存所有素数
    int count = 0;

    memset(is_comp, 0, sizeof(is_comp));

    for (int i = 2; i <= N; i++) {
        if (!is_comp[i]) {
            primes[count++] = i;   // 这个数没被划掉，是素数
        }
        for (int j = 0; j < count; j++) {
            int p = primes[j];
            if (i * p > N) break;  // 超出范围就别划了
            is_comp[i * p] = 1;    // 划掉这个合数
            if (i % p == 0) break; // 一旦被这个质数整除，就停
        }
    }

    printf("200以内的素数：\n");
    for (int i = 0; i < count; i++) {
        printf("%d ", primes[i]);
    }
    printf("\n");
    return 0;
}

🎯 一句话总结

版本 规则 重复划吗 速度
暴力试除 一个个除 很多 最慢
埃式筛 一个素数划所有倍数 有点重复 快
线性筛 每个合数只被最小质因子划一次 不重复 最快

如果你能记住一句话，你就懂线性筛了：

“每个数只让它的第一个质因子出手一次。”

要不要我帮你画成一张表格（比如1到30）告诉你每个数是被谁“干掉”的？那张表会让你彻底看懂原理。

您说：

我理解他的逻辑但是我不理解为什么是这么做的

ChatGPT 说：

非常好，这个问题说明你已经不只是“会抄算法”，而是真的想理解它的逻辑根源。
我来用非常通俗的方式告诉你，为什么线性筛要“这么做”，而且“这么做就对了”。

🧠 一句话先定调

线性筛的那句核心代码：

1
if (i % p == 0) break;

其实就是在控制——
👉 每个合数，只被“它的最小质因子”负责一次。
这就是整个算法的灵魂。
下面我分成三个阶段帮你想透它。

🧩 一、回忆一下埃式筛的问题

埃式筛干的活是：

  • 每发现一个素数，就去划它的倍数。
  • 比如 12 会被谁划？
    • 被 2 划一次（2×6）
    • 被 3 又划一次（3×4）
    • 被 4 还可能划（虽然4不是素数）

这就叫“重复劳动”。
埃式筛虽然已经很快，但它对每个合数都可能划很多次。

🧩 二、那我们能不能让每个合数只被“一个人”划？

我们希望：

  • 12 只被 2 处理一次；
  • 18 只被 3 处理一次；
  • 25 只被 5 处理一次。

那怎么办？
我们规定：

一个合数只能被它的最小质因子负责。

🧩 三、算法的关键思想：i × p

我们从小到大枚举 i，然后拿素数表里的质数去乘它。

每当我们在循环中计算：

1
i * p

这个结果就是一个合数。
那这个合数的最小质因子是谁？
答案：一定是 p。

为什么？看下面的分析。

🔍 情况1：i 没有被 p 整除

比如 i = 9, p = 2。
→ i * p = 18。
18 的质因子有 2, 3, 6…
最小质因子确实是 2。✅
说明标记 18 的动作是正确的。

🔍 情况2：i 能被 p 整除

比如 i = 6, p = 2。
→ i * p = 12。
12 的质因子里，最小质因子也是 2。✅
所以标记 12 这次没问题。

但再往后如果我用 p=3，再标一次：
i = 6, p = 3 → i*p = 18。
18 的最小质因子其实是 2，不是 3。
那 18 已经在“2”那轮被标过了，
这次再标就是重复劳动。❌

所以，我们一旦发现 i 已经被 p 整除（i % p == 0），
我们就知道：

“再往后的质数都会比 p 大，它们标出来的乘积 ip’ 的最小质因子仍然是 p。”
于是我们*立即停下。

⚙️ 用人话总结整个逻辑链

阶段 含义
1 我们要标出所有合数。
2 每个合数应该只被它的最小质因子标一次。
3 枚举 i，并用所有质数 p 去乘 i。
4 当 i%p==0 时，说明 p 是 i 的最小质因子。
5 那 i*p 也一定以 p 为最小质因子；更大的质数乘它都是重复。
6 所以我们停下。

这就是为什么“这么做”是正确的。

🎯 一句话记死：

“因为 i 是被从小到大遍历的，所以当 i%p==0 时，p 一定是 i 的最小质因子。
所以 i*p 的最小质因子也是 p。
因此它只该被 p 这一轮标记一次，之后全跳过。”

💡 对比图（简化）：

数 最小质因子 谁标的
4 2 2×2
6 2 3×2
9 3 3×3
10 2 5×2
15 3 5×3
25 5 5×5

每个合数，只出现一次标记，完美。

你现在的感觉可能是：“哦——它不是魔法，是逻辑顺序决定的！”
没错。线性筛看起来像“有技巧”，其实它只是精确地利用了：

“从小到大遍历 + 最小质因子规律”。

要不要我帮你画出一个“6×6 的乘法表”，
在上面标出哪些格子会被线性筛划掉、哪些会被跳过？
那张表一看就能直观理解“为什么停得刚刚好”。

您说：

为什么因为 6%2==0 → 停

ChatGPT 说：

这句“因为 6%2==0 → 停”，是整个线性筛的灵魂，但第一次看到确实容易懵。
别怕，我们不讲数学名词，就用生活比喻让你一秒懂。

🎯 我们先说结论：

当 i % p == 0，说明 p 已经是 i 的最小质因子，
所以任何比 p 更大的质数再去乘 i，得到的结果都会“被多次标记”，
我们要及时“刹车”。

🧩 用现实比喻理解：

想象你在工厂贴标签。

  • 每个数代表一个产品编号。
  • 每个素数代表一个“质检员”。
  • 合数的工作是：要被它的第一个能整除它的质检员打上“非合格”标签。

工厂规定：

任何产品只允许被最小质检员打一次标签，别重复浪费时间。

现在你是检查员，轮到你在看 i = 6 这件产品。

你的质检员名单是 [2, 3, 5, 7...]。

开始干活：

  1. 第一个质检员 2 来检查：
    • 6%2==0 → “哦，这件产品（6）能被我整除，所以我是它的最小质因子。”
    • 于是他打上标签，并负责它的“后代产品”：6*2=12。
    • 打完后，他喊：“后面的人别来了，这活我干完了。”
    • 所以你 break 停止循环。
  2. 如果你不停止，后面的质检员（3、5、7）还会来：
    • 3 会再标 18
    • 5 会再标 30
    • 但这些数的最小质因子都是 2，本该在 2 那一轮就被标过。
    • 所以他们做的都是重复劳动。

🧮 换成数学语言：

当我们在循环：

1
2
3
4
5
6
for (int j = 0; j < count; j++) {
    int p = primes[j];
    if (i * p > N) break;
    is_comp[i * p] = 1;
    if (i % p == 0) break;
}

这里的意思就是：

  • 对每个 i，我们拿质数 p 去生成新数 i*p。
  • 但一旦 i 能被 p 整除：
    • 那说明 p 是 i 的最小质因子。
    • 那 i*p 的最小质因子也一定是 p（而不是别的质数）。
    • 所以之后再用更大的质数 q 去乘 i（比如 iq），
      那个结果 i      q 的最小质因子仍然是 p，而不是 q。
      它以后会在“p 那轮”被标，不归你这轮负责。
    • 所以我们直接停下，不再继续循环。

🧱 举例说明（实打实的数字）：

i = 6，素数表 [2,3,5]

p i*p i%p 说明
2 12 0 2 是 6 的最小质因子 → 停
3 18 （没机会执行） 本来该由 2 那轮标掉
5 30 （也不用标） 同上

结果：12 被标一次，18、30 由别的人标，不重复。

💡 再看一个不会停的例子：

i = 9，素数表 [2,3,5]

p i*p i%p 说明
2 18 ≠0 继续，因为 2 不是 9 的因子
3 27 =0 3 是 9 的最小质因子 → 停
5 （不执行）

这样就保证了：

  • 18 被 2 标一次。
  • 27 被 3 标一次。
  • 没有人重复干活。

🧩 一句话总结：

“当 i 能被 p 整除时，p 已经是 i 的最小质因子，
所以后面的质数就不该再碰 i 的倍数，
否则他们会抢活干，浪费时间。”

你可以把那句 if (i % p == 0) break; 想成工厂里的“禁止重复贴标签”按钮。
按下去，就代表“这批货我负责，后面的别动”。

这，就是线性筛为什么这么做。