C++素数筛法：埃氏筛与线性筛对比与实现

1. 筛法基础与算法选择

在C++编程竞赛和等级考试中，素数筛选是高频考点。埃氏筛（Sieve of Eratosthenes）和线性筛（欧拉筛）作为两种经典算法，各有其适用场景。埃氏筛时间复杂度为O(n log log n)，适合快速生成小规模素数表；线性筛则通过最小质因数优化，达到严格的O(n)时间复杂度，适合处理大规模数据。

1.1 算法核心思想对比

埃氏筛的工作机制是从2开始，将每个素数的倍数标记为合数。例如处理数字2时，会标记4、6、8等所有2的倍数为非素数。这种"批量标记"的方式导致部分合数会被重复标记（如6会被2和3同时标记），这是其效率瓶颈所在。

线性筛通过两个关键改进解决这个问题：

1. 每个合数仅被其最小质因数筛除一次
2. 使用已筛选的素数列表作为基数

具体实现时，算法维护一个素数数组prime[]，对每个数i，用所有不大于i最小质因数的素数p去筛i*p。当i%p==0时立即终止内层循环，确保每个合数只被标记一次。

2. 埃氏筛实现详解

2.1 标准实现代码

cpp复制#include <vector>
using namespace std;

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

2.2 关键优化技巧

1. 外层循环优化：只需遍历到√n即可，因为更大数的倍数已被更小的素数处理
2. 内层循环起点：从i²开始标记，避免重复处理i*(i-1)等已被标记的数
3. **