🎯 素数大揭秘：埃氏筛 & 线性筛的魔法课堂

—— 青少年信息学竞赛入门系列 · 第①讲

🧠 什么是素数？

在数学的王国里，有一类数特别“孤傲”——它们除了 1 和自己，谁也不认识。

比如：

• 2、3、5、7、11、13……这些都是 素数（Prime Number）

• 而 4=2×2，6=2×3，9=3×3……这些叫 合数（Composite Number）

🧩 小测试：
以下哪些是素数？
👉 17，21，23，27，29

答案：✅ 17, 23, 29 是素数；❌ 21, 27 是合数

🔍 如何快速找出素数？

从 1 到 10 万中找素数，数一个算一个？太慢！
于是，数学家们发明了两种“批量筛选”的绝招：

🌀 第一招：埃拉托色尼筛法

（英文名：Eratosthenes Sieve）

📖 思想：

每当遇到一个素数，就把它的倍数全部划掉，留下的就是素数！

🎨 举个例子（1~30）：

• 2 是素数 → 划掉 4,6,8,...

• 3 是素数 → 划掉 6,9,12,...

• 5 是素数 → 划掉 10,15,20,...

最后剩下的就是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ✅

✅ 方法一：埃拉托色尼筛法（Eratosthenes）

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

const int N = 1e6 + 10;       // 筛选范围上限
bool is_prime[N];            // 标记数组，is_prime[i] == true 表示 i 是素数

// 埃氏筛法实现
void eratosthenes(int n) {
    fill(is_prime, is_prime + n + 1, true); // 初始化全部为 true
    is_prime[0] = is_prime[1] = false;      // 0 和 1 不是素数

    for (int i = 2; i <= sqrt(n); ++i) {
        if (is_prime[i]) {
            // 将 i 的所有倍数标记为非素数
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

int main() {
    int n;
    cout << "请输入筛选素数的范围上限（如 1000000）：";
    cin >> n;

    eratosthenes(n); // 调用筛法

    cout << "前100个素数为：" << endl;
    int count = 0;
    for (int i = 2; i <= n && count < 100; ++i) {
        if (is_prime[i]) {
            cout << i << " ";
            count++;
        }
    }
    cout << endl;
    return 0;
}

⚡ 第二招：线性筛法（欧拉筛）

📖 思想：

每个合数，只被它的最小质因子标记一次，绝不重复！

🧠 什么是“最小质因子”？
比如：

• 6 = 2×3 → 最小质因子是 2

• 15 = 3×5 → 最小质因子是 3

• 77 = 7×11 → 最小质因子是 7

✅ 方法二：线性筛法（欧拉筛）

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

const int N = 1e6 + 10;
bool is_prime[N];           // is_prime[i] == false 表示 i 是素数
vector<int> primes;         // 存储素数列表

// 线性筛实现：每个合数只被其最小质因子标记一次
void linear_sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!is_prime[i]) {
            primes.push_back(i); // i 是素数
        }
        for (int p : primes) {
            if (p * i > n) break;
            is_prime[p * i] = true; // 标记合数

            // 如果 p 是 i 的最小质因子，则跳出，保证每个合数只被标记一次
            if (i % p == 0) break;
        }
    }
}

int main() {
    int n;
    cout << "请输入筛选素数的范围上限（如 1000000）：";
    cin >> n;

    linear_sieve(n); // 调用线性筛法

    cout << "前100个素数为：" << endl;
    for (int i = 0; i < 100 && i < primes.size(); ++i) {
        cout << primes[i] << " ";
    }
    cout << endl;
    return 0;
}

💡 亮点：

• 不重复标记，效率更高

• 时间复杂度是 $O(n)，适合数据量超大的场景

🧮 对比总结表