素数筛法详解：埃氏筛与线性筛的比较与实现

1. 素数筛法概述

在计算机科学和数学领域，素数筛法是一种用于快速生成素数列表的高效算法。对于准备GESP C++五级考试的学生来说，掌握埃氏筛和线性筛这两种经典算法至关重要。这两种筛法不仅能帮助我们快速求解素数问题，更是理解算法优化思想的绝佳案例。

素数筛法的核心思想是通过逐步排除合数来筛选素数。与传统的逐个判断法相比，筛法通过批量处理大幅提高了效率。例如，要找出1,000,000以内的所有素数，传统方法需要对每个数进行素数测试，时间复杂度高达O(n√n)，而筛法可以将复杂度降低到接近线性。

2. 埃氏筛法详解

2.1 算法原理与实现步骤

埃氏筛法（Sieve of Eratosthenes）是最古老的素数筛法，由古希腊数学家埃拉托斯特尼在公元前3世纪提出。其核心思想是：从2开始，将每个素数的所有倍数标记为合数。

具体实现步骤如下：

1. 初始化一个布尔数组isPrime[0..n]，全部设为true
2. 从i=2开始遍历到√n：
   • 如果isPrime[i]为true，则i是素数
   • 将i的所有倍数（从i²开始）标记为false
3. 最后，所有isPrime值为true的索引即为素数

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

const int N = 1000000;
bool isPrime[N+1];

void eratosthenesSieve(int n) {
    for(int i=2; i<=n; i++) isPrime[i] = true;
    
    for(int i=2; i*i<=n; i++) {
        if(isPrime[i]) {
            for(int j=i*i; j<=n; j+=i) {
                isPrime[j] = false;
            }
        }
    }
    
    for(int i=2; i<=n; i++) {
        if(isPrime[i]) cout << i << " ";
    }
}

2.2 关键优化点解析

埃氏筛法有几个重要的优化点值得注意：

1. 从i²开始标记：对于素数i，比i²小的倍数（如i×2, i×3,...,i×(i-1)）已经被更小的素数标记过了。例如，当i=5时，10(5×2)已经被2标记，15(5×3)已经被3标记，因此直接从25(5×5)开始即可。

2. 只需遍历到√n：任何合数n都至少有一个质因数小于等于√n。因此，筛到√n时，所有合数都已被正确标记。

3. 内存优化：可以使用位运算来压缩存储空间，将布尔数组转换为位图，可以节省7/8的内存。

2.3 时间复杂度分析

埃氏筛法的时间复杂度为O(n log log n)，这个结果来自于数论中的Mertens定理。虽然看起来比线性时间慢，但对于n≤10⁶的情况已经足够高效。

实际测试表明，在普通计算机上：

• n=10⁶时，执行时间约10ms
• n=10⁷时，执行时间约100ms
• n=10⁸时，执行时间约1s

3. 线性筛法（欧拉筛）详解

3.1 算法原理与实现

线性筛法（又称欧拉筛）由著名数学家欧拉提出，其核心思想是确保每个合数只被其最小质因数筛除一次，从而将时间复杂度优化到真正的O(n)。

实现要点：

1. 维护一个素数列表prime[]
2. 对于每个数i，用已知素数prime[j]去筛i×prime[j]
3. 当i能被prime[j]整除时停止，确保每个合数只被筛一次

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

const int N = 1000000;
int prime[N], cnt = 0;
bool vis[N+1];

void eulerSieve(int n) {
    for(int i=2; i<=n; i++) {
        if(!vis[i]) prime[cnt++] = i;
        
        for(int j=0; j<cnt && i*prime[j]<=n; j++) {
            vis[i*prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
    
    for(int i=0; i<cnt; i++) {
        cout << prime[i] << " ";
    }
}

3.2 关键点：if(i%prime[j]==0) break

这是线性筛法的核心优化点，它确保了每个合数只被筛一次。具体原理：

1. 当i%prime[j]==0时，说明prime[j]是i的最小质因数
2. 此时i可以表示为i = prime[j] × k
3. 对于更大的prime[m]（m>j），i×prime[m] = prime[j] × (k×prime[m])
4. 这个数应该在后面当i=k×prime[m]时，用prime[j]来筛
5. 因此现在可以停止，避免重复筛除

3.3 时间复杂度与性能对比

线性筛法的时间复杂度严格为O(n)，因为每个合数只被访问一次。实际性能对比：

虽然在小数据量时差异不大，但当n≥10⁷时，线性筛的优势开始显现。

4. 两种筛法的比较与选择

4.1 算法特性对比

4.2 实际应用建议

1. 教学场景：建议先学习埃氏筛，理解筛法的基本思想，再学习线性筛
2. 编程竞赛：对于大部分题目，埃氏筛足够使用且更易实现
3. 大数据场景：当n≥10⁷时，应优先选择线性筛
4. 内存敏感场景：可以使用埃氏筛的位运算优化版

4.3 常见问题与调试技巧

1. 数组越界问题：确保数组大小足够（通常设为n+1）
2. 初始值设置：记得初始化isPrime或vis数组
3. 输出范围：注意题目要求的输出范围（如是否包含n）
4. 性能优化：对于C++，使用iostream可能比cstdio慢，在极端优化时可以考虑切换

调试时可以输出中间结果：

cpp复制// 调试输出
cout << "筛除 " << i*prime[j] << " 使用素数 " << prime[j] << endl;

5. 算法扩展与应用

5.1 筛法求欧拉函数

线性筛法可以扩展用于计算欧拉函数φ(n)，即小于n且与n互质的数的个数：

cpp复制int phi[N];
void eulerPhiSieve(int n) {
    for(int i=2; i<=n; i++) {
        if(!vis[i]) {
            prime[cnt++] = i;
            phi[i] = i-1;
        }
        for(int j=0; j<cnt && i*prime[j]<=n; j++) {
            vis[i*prime[j]] = true;
            if(i%prime[j] == 0) {
                phi[i*prime[j]] = phi[i] * prime[j];
                break;
            } else {
                phi[i*prime[j]] = phi[i] * (prime[j]-1);
            }
        }
    }
}

5.2 筛法求莫比乌斯函数

类似地，可以计算莫比乌斯函数μ(n)：

cpp复制int mu[N];
void mobiusSieve(int n) {
    mu[1] = 1;
    for(int i=2; i<=n; i++) {
        if(!vis[i]) {
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for(int j=0; j<cnt && i*prime[j]<=n; j++) {
            vis[i*prime[j]] = true;
            if(i%prime[j] == 0) {
                mu[i*prime[j]] = 0;
                break;
            } else {
                mu[i*prime[j]] = mu[i] * -1;
            }
        }
    }
}

5.3 区间筛法

对于超大区间[a,b]的素数筛选，可以使用分段筛法：

1. 先用普通筛法求出√b以内的素数
2. 用这些素数去筛区间[a,b]内的合数
3. 剩下的就是区间内的素数

这种方法可以处理如[10¹², 10¹²+10⁶]这样的大区间问题。

在实际编程中，理解筛法不仅是为了解决素数问题，更是培养算法优化思维的重要途径。从埃氏筛到线性筛的演进，体现了计算机科学中"减少重复计算"的核心思想，这种思想在动态规划、记忆化搜索等高级算法中都有广泛应用。