📘 数论基础：素数判断与质数筛法总结

---

🔢 基本定义

• 质数（素数）：大于 1 的自然数，除了 1 和它本身，没有其他因数。
• 合数：大于 1 且有除了 1 和自身外的因数的自然数。
• 最小质因数：一个合数中最小的质因数。

---

🔍 素数判断方法

✅ 普通判断（试除法）

• 从 2 到 √n 遍历，如果 n 能被整除则不是素数。
• 时间复杂度：O(√n)
• 用于判断单个整数是否为素数。

bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0) return false;
    return true;
}

🧹 质数筛法（批量找出素数） 📌 筛法简介 用于快速找出某个范围内所有的素数。

核心思想：通过标记合数来“筛”出素数。

🧮 筛法分类

1️⃣ 埃拉托斯特尼筛法（埃氏筛）

基本思想：从 2 开始，将每个数的倍数标记为合数。

实现简单，容易理解，但标记倍数存在重复。

时间复杂度：O(n log log 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 = i * i; j <= n; j += i)
            is_prime[j] = false;
    }
}

2️⃣ 线性筛法（欧拉筛）

基本思想：每个合数只被其最小质因数筛去一次。

时间复杂度：O(n)，效率更高。

稍微复杂但适合大规模素数筛选。

vector<int> primes;
vector<bool> is_prime(n + 1, true);
for (int i = 2; i <= n; ++i) {
    if (is_prime[i]) primes.push_back(i);
    for (int p : primes) {
        if (p * i > n) break;
        is_prime[p * i] = false;
        if (i % p == 0) break;
    }
}

⚙️ 筛法优化策略 范围优化：只筛到 √n 即可。

埃式筛：从 i*i 开始标记更高效。

欧拉筛：一旦 i % p == 0，就跳出内层循环，避免重复标记。

🧠 应用场景 求某范围内的质数总数

获取一个数的所有质因数

加密算法中生成大素数（如 RSA）

高效求解数论类竞赛题（如因子、最小质因数）

✅ 小结对比 方法 时间复杂度 是否重复标记 实现复杂度 适用范围 试除法 O(√n) N/A 简单 判断单个数是否为素数 埃式筛法 O(n log log n) 有 简单 小范围素数筛选 线性筛法 O(n) 无 中等 大范围高效筛选