质数筛法详解：从枚举到线性筛的高效实现

1. 质数筛法概述：从基础到高效算法

在计算机科学和数学领域，质数筛法是一类用于高效找出一定范围内所有质数的算法。作为编程竞赛和算法学习的基础内容，质数筛法在GESP五级考试、蓝桥杯等编程赛事中都是重要考点。

质数（又称素数）是指大于1的自然数中，除了1和它本身外不再有其他因数的数。理解质数的性质对于学习数论和密码学等高级主题至关重要。在实际编程中，我们经常需要快速判断一个数是否为质数，或者获取某个范围内的所有质数。这时候，高效的质数筛法就显得尤为重要。

常见的质数判断方法有三种：最基础的枚举法、改进的埃拉托斯特尼筛法（简称埃氏筛），以及更高效的欧拉筛（线性筛）。这三种方法在时间复杂度和实际应用场景上有着显著差异，理解它们的原理和实现对于编程学习者来说是非常有价值的。

2. 基础方法：枚举法及其优化

2.1 枚举法的基本实现

枚举法是最直观的质数判断方法。其核心思想是：对于一个数n，检查从2到n-1的所有整数是否能整除n。如果存在任何一个数能整除n，则n不是质数；否则，n是质数。

cpp复制bool isPrime(int n) {
    if(n == 1) return false;  // 1不是质数
    if(n == 2) return true;   // 2是唯一的偶质数
    
    for(int i = 2; i < n; i++) {
        if(n % i == 0) 
            return false;  // 发现能整除的因子，不是质数
    }
    
    return true;  // 没有找到能整除的因子，是质数
}

这种方法虽然简单直接，但效率很低。对于每个数n，都需要进行n-2次取模运算，当n很大时，这会消耗大量计算资源。

2.2 枚举法的优化思路

我们可以通过数学观察来优化枚举法。注意到如果一个数n不是质数，那么它至少有一个因子小于等于√n。因此，我们只需要检查2到√n的范围即可。

cpp复制bool isPrimeOptimized(int n) {
    if(n == 1) return false;
    if(n == 2) return true;
    
    int sqrt_n = sqrt(n);  // 计算平方根，避免重复计算
    for(int i = 2; i <= sqrt_n; i++) {
        if(n % i == 0)
            return false;
    }
    return true;
}

这个优化将时间复杂度从O(n)降低到了O(√n)，对于大数判断来说效率提升显著。例如，判断100000是否为质数，原始方法需要99998次循环，而优化后只需316次循环。

2.3 枚举法的局限性

尽管优化后的枚举法在判断单个数的质数性质时效率不错，但当我们需要找出一个范围内所有质数时，这种方法就显得力不从心了。例如，要找出1到100000之间的所有质数，使用枚举法需要对每个数单独判断，总体时间复杂度为O(n√n)，这在n较大时仍然不够高效。

3. 埃拉托斯特尼筛法（埃氏筛）

3.1 埃氏筛的基本原理

埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种更高效的质数筛选算法，由古希腊数学家埃拉托斯特尼提出。其核心思想是：

1. 假设所有数初始都是质数（未被筛掉）
2. 从第一个质数2开始，将其所有倍数标记为非质数（筛掉）
3. 找到下一个未被筛掉的数，它一定是质数，然后筛掉它的所有倍数
4. 重复步骤3，直到处理完所有数

这种方法之所以高效，是因为它利用了质数的倍数必然是非质数这一性质，通过批量标记的方式减少了重复判断。

3.2 埃氏筛的详细实现

下面是一个用C++实现的埃氏筛示例：

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

vector<int> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);  // 初始假设所有数都是质数
    vector<int> primes;
    
    isPrime[0] = isPrime[1] = false;  // 0和1不是质数
    
    for(int i = 2; i <= n; i++) {
        if(isPrime[i]) {  // 如果i是质数
            primes.push_back(i);  // 加入质数列表
            
            // 标记i的所有倍数为非质数
            for(int j = i * 2; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    return primes;
}

3.3 埃氏筛的时间复杂度分析

埃氏筛的时间复杂度为O(n log log n)，这比枚举法的O(n√n)要好得多。这个复杂度来自于以下数学事实：

对于每个质数p，我们需要标记n/p个它的倍数。因此总操作次数约为：
n/2 + n/3 + n/5 + n/7 + ... + n/p (p ≤ √n)

这个级数的和渐进于n log log n，因此埃氏筛的时间复杂度为O(n log log n)。

3.4 埃氏筛的优化空间

虽然埃氏筛已经很高效，但我们还可以进行一些优化：

1. 外层循环只需要遍历到√n，因为任何大于√n的数的倍数都已经被更小的质数筛过了
2. 内层循环可以从i²开始，而不是从2i开始，因为更小的倍数已经被之前的质数筛过了

优化后的实现：

cpp复制vector<int> optimizedSieve(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;
    
    isPrime[0] = isPrime[1] = false;
    
    for(int i = 2; i * i <= n; i++) {  // 只需遍历到√n
        if(isPrime[i]) {
            for(int j = i * i; j <= n; j += i) {  // 从i²开始标记
                isPrime[j] = false;
            }
        }
    }
    
    // 收集所有质数
    for(int i = 2; i <= n; i++) {
        if(isPrime[i]) {
            primes.push_back(i);
        }
    }
    
    return primes;
}

3.5 埃氏筛的局限性

尽管埃氏筛已经很高效，但它仍然存在一个主要问题：重复标记。例如，数字30会被质数2、3、5各标记一次。当n很大时，这种重复标记会浪费不少时间。这就引出了我们接下来要介绍的更高效的算法——欧拉筛（线性筛）。

4. 欧拉筛（线性筛）

4.1 线性筛的基本原理

欧拉筛（Euler's Sieve），又称线性筛，是一种时间复杂度为O(n)的质数筛法。它的核心思想是：确保每个合数只被它的最小质因子筛掉一次，从而避免重复标记。

线性筛的关键在于：对于每个数i，用所有已知的质数p去筛i×p，但当i能被p整除时立即停止。这样可以保证每个合数只被它的最小质因子筛掉。

4.2 线性筛的详细实现

下面是线性筛的C++实现：

cpp复制vector<int> linearSieve(int n) {
    vector<bool> isComposite(n + 1, false);  // 标记是否为合数
    vector<int> primes;
    
    for(int i = 2; i <= n; i++) {
        if(!isComposite[i]) {  // i是质数
            primes.push_back(i);
        }
        
        // 用当前质数表筛i的倍数
        for(int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            isComposite[i * primes[j]] = true;  // 标记为合数
            
            // 关键步骤：如果i能被当前质数整除，就停止
            if(i % primes[j] == 0) {
                break;
            }
        }
    }
    
    return primes;
}

4.3 线性筛的关键步骤解析

线性筛中最关键的一行代码是：

cpp复制if(i % primes[j] == 0) break;

这行代码确保了每个合数只被它的最小质因子筛掉。具体来说：

1. 当i % primes[j] == 0时，说明primes[j]是i的最小质因子
2. 那么对于i × primes[j+1]，它的最小质因子应该是primes[j]而不是primes[j+1]
3. 因此我们应该停止当前循环，让i × primes[j+1]在后续被primes[j]筛掉

这个机制保证了每个合数只被筛一次，从而实现了线性时间复杂度。

4.4 线性筛的时间复杂度分析

线性筛的时间复杂度确实是O(n)，这是因为：

1. 外层循环遍历每个数i，共n-1次
2. 内层循环对于每个i，最多执行其质因子个数次
3. 根据数论结果，1到n的数的质因子个数平均为O(1)级别
4. 因此总操作次数为O(n)

4.5 线性筛与埃氏筛的比较

5. 实际应用与问题解决

5.1 解决洛谷P5736质数筛问题

让我们回到最初的洛谷P5736问题：给定n个正整数，筛除其中的非质数，输出剩余的质数。使用线性筛的解决方案如下：

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

const int MAX_N = 1e5;

vector<int> getPrimes() {
    vector<bool> isComposite(MAX_N + 1, false);
    vector<int> primes;
    
    for(int i = 2; i <= MAX_N; i++) {
        if(!isComposite[i]) {
            primes.push_back(i);
        }
        for(int j = 0; j < primes.size() && i * primes[j] <= MAX_N; j++) {
            isComposite[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
        }
    }
    
    return primes;
}

int main() {
    // 预处理所有质数
    vector<int> primes = getPrimes();
    vector<bool> isPrime(MAX_N + 1, false);
    for(int p : primes) {
        isPrime[p] = true;
    }
    
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        int num;
        cin >> num;
        if(isPrime[num]) {
            cout << num << " ";
        }
    }
    
    return 0;
}

这个解决方案的关键点在于：

1. 预处理阶段使用线性筛找出1e5范围内的所有质数
2. 创建一个布尔数组快速判断某个数是否为质数
3. 对于输入的每个数，直接查表判断是否为质数

5.2 性能对比实测

为了直观展示不同算法的性能差异，我在本地进行了测试（环境：Intel i7-9700K，16GB RAM）：

从测试结果可以看出，随着n的增大，线性筛的优势越来越明显。特别是当n=1e8时，线性筛比埃氏筛快了近一倍。

5.3 常见问题与调试技巧

在实现质数筛法时，初学者常会遇到以下问题：

1. 数组越界：忘记处理n=1或n=0的情况，或者在标记倍数时超出数组范围

   • 解决方法：确保数组大小为n+1，并正确处理边界情况

2. 重复标记导致性能下降：在埃氏筛中没有优化内层循环的起始点

   • 解决方法：从i²开始标记，而不是从2i开始

3. 线性筛的关键条件遗漏：忘记添加if(i % primes[j] == 0) break;

   • 解决方法：仔细理解线性筛的原理，确保实现完整

4. 空间不足：当n很大时，使用过大的数据结构

   • 解决方法：考虑使用位运算压缩存储空间，或者分段筛法

调试时可以先用小范围的n（如n=30）手动验证算法的正确性，再逐步增大n测试性能。

6. 算法扩展与应用

6.1 筛法求最小质因子

线性筛不仅可以用来找出所有质数，还可以稍作修改来记录每个数的最小质因子，这在数论算法中非常有用：

cpp复制vector<int> getMinPrimeFactors(int n) {
    vector<int> minPrime(n + 1, 0);
    vector<int> primes;
    
    for(int i = 2; i <= n; i++) {
        if(minPrime[i] == 0) {  // i是质数
            minPrime[i] = i;    // 质数的最小质因子是它自己
            primes.push_back(i);
        }
        
        for(int j = 0; j < primes.size() && primes[j] <= minPrime[i] && i * primes[j] <= n; j++) {
            minPrime[i * primes[j]] = primes[j];
        }
    }
    
    return minPrime;
}

6.2 筛法求欧拉函数

欧拉函数φ(n)表示小于等于n的正整数中与n互质的数的个数。利用线性筛可以高效计算欧拉函数：

cpp复制vector<int> eulerPhiSieve(int n) {
    vector<int> phi(n + 1);
    vector<int> primes;
    vector<bool> isComposite(n + 1, false);
    
    phi[1] = 1;
    
    for(int i = 2; i <= n; i++) {
        if(!isComposite[i]) {
            primes.push_back(i);
            phi[i] = i - 1;  // 质数的欧拉函数值为i-1
        }
        
        for(int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            isComposite[i * primes[j]] = true;
            
            if(i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];  // 情况1
                break;
            } else {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);  // 情况2
            }
        }
    }
    
    return phi;
}

6.3 分段筛法处理超大范围

当我们需要筛的n非常大（比如1e12）时，内存可能无法容纳整个筛表。这时可以使用分段筛法：

1. 先用普通筛法筛出√n以内的所有质数
2. 将大区间分成适当大小的段
3. 对每一段，用筛出的质数来标记段内的合数
4. 剩下的未标记的数就是质数

分段筛法虽然速度稍慢，但可以处理内存无法容纳整个筛表的超大范围问题。

7. 算法选择建议与总结

在实际应用中，如何选择合适的质数筛法呢？以下是我的建议：

1. 小范围判断（n<1e6）：优化后的枚举法可能就足够了，实现简单
2. 中等范围（1e6<n<1e7）：埃氏筛实现简单，性能可以接受
3. 大范围（n>1e7）：线性筛是最佳选择，性能最优
4. 超大范围（n>1e12）：考虑分段筛法或其他高级筛法

质数筛法是算法学习中的经典内容，理解这些算法的原理和实现对于提升编程能力和算法思维很有帮助。在实际编程竞赛中，线性筛因其优异的性能常常是首选。

我在实际使用中发现，线性筛的实现虽然稍复杂，但一旦掌握，可以解决许多与质数相关的问题。特别是在处理需要频繁查询质数性质的问题时，预处理+查表的方式效率极高。