C++新手必看：三种质数筛法（暴力、埃氏、线性）的性能对比与实战选择

C++质数筛法实战指南：从暴力到线性的算法进化与选择策略

在算法竞赛和编程面试中，质数筛法是一个永恒的话题。当你面对"判断1e6以内的所有质数"这样的问题时，选择不同的算法可能导致运行时间从几秒到几毫秒的天壤之别。本文将从实际OJ题目场景出发，带你深入理解三种经典质数筛法——暴力筛、埃拉托斯特尼筛（埃氏筛）和欧拉筛（线性筛）的内在机理与性能差异。

1. 算法竞赛中的质数问题典型场景

质数相关问题在编程竞赛中出现的频率极高。以蓝桥杯历年真题为例，几乎每届都会出现至少一道与质数相关的题目。常见的问题形式包括：

• 统计某个区间内的质数数量（如[1,1e6]）
• 寻找满足特定条件的质数（如回文质数、孪生质数）
• 质因数分解相关问题
• 基于质数的数学问题（如哥德巴赫猜想变种）

这些问题看似简单，但当数据规模达到1e6甚至1e7时，算法选择就变得至关重要。我曾在一个区域赛中因为使用了暴力筛法而超时，后来改用线性筛后同样的问题在1/10的时间内就解决了。

2. 三种质数筛法的原理与实现

2.1 暴力筛法：最直观的入门选择

暴力筛法的思路简单直接：对于每个数n，检查它是否能被2到√n之间的任何整数整除。如果不能，则n是质数。

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

时间复杂度分析：

• 单个数字检查：O(√n)
• 检查1到n的所有数字：O(n√n)

适用场景：

• 小范围数据（n ≤ 1e4）
• 只需要检查少量数字是否为质数
• 编程初学者理解质数概念

实际测试数据：

2.2 埃氏筛法：平衡效率与复杂度的经典选择

埃氏筛法通过标记倍数的方式高效筛选质数，其核心思想是：每个质数的倍数都不是质数。

vector<bool> sieve_eratosthenes(int 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; } } } return is_prime; }

优化技巧：

1. 从i*i开始标记，因为更小的倍数已经被更小的质数标记过
2. 外层循环只需到√n

时间复杂度分析：

• 理论复杂度：O(n log log n)
• 实际运行效率接近线性

适用场景：

• 中等规模数据（n ≤ 1e7）
• 需要预处理质数表的题目
• 内存受限环境（相比线性筛更节省空间）

2.3 线性筛法：极致性能的终极选择

线性筛法（欧拉筛）通过确保每个合数只被其最小质因数筛除，达到了O(n)的时间复杂度。

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

关键点解析：

• if (i % primes[j] == 0) break确保每个合数只被筛一次
• 内层循环对每个i都执行，不仅限于质数

时间复杂度分析：

• 严格O(n)，每个合数只被标记一次

适用场景：

• 大规模数据（n ≥ 1e7）
• 需要同时获取质数表和最小质因数表
• 对时间要求极其严格的题目

3. 性能对比与选择策略

3.1 理论性能对比

3.2 实际运行时间对比

以下是在相同环境下的测试结果（单位：毫秒）：

提示：当n=1e7时，暴力筛法已经需要约150秒，不适合实际使用

3.3 算法选择决策树

根据题目要求选择合适的算法：

1. 是否需要预处理质数表？

   • 否 → 考虑暴力筛法（仅适用于极小数据）
   • 是 → 进入下一步

2. 数据规模有多大？

   • n ≤ 1e6 → 埃氏筛法（实现简单）
   • 1e6 < n ≤ 1e7 → 根据时间限制选择
   • n > 1e7 → 线性筛法

3. 是否需要额外信息？

   • 需要最小质因数 → 线性筛法
   • 只需要质数判断 → 埃氏筛法

4. 内存限制严格？

   • 是 → 埃氏筛法（可用位优化）
   • 否 → 线性筛法

4. 实战应用与常见陷阱

4.1 典型题目解析

题目：统计区间质数数量（LeetCode 204）

给定整数n，统计所有小于非负整数n的质数的数量。

解决方案比较：

1. 暴力解法（超时）：

int countPrimes_brute(int n) { int count = 0; for (int i = 2; i < n; ++i) { if (isPrime_brute(i)) ++count; } return count; }

2. 埃氏筛解法（推荐）：

int countPrimes_eratosthenes(int n) { if (n <= 2) return 0; vector<bool> is_prime(n, true); int count = n - 2; // 排除0和1 for (int i = 2; i * i < n; ++i) { if (is_prime[i]) { for (int j = i * i; j < n; j += i) { if (is_prime[j]) { is_prime[j] = false; --count; } } } } return count; }

4.2 常见错误与调试技巧

1. 边界条件处理不当

   • 忘记处理0和1的非质数情况
   • 循环条件错误（如ii<=n还是ii<n）

2. 性能陷阱

   • 在埃氏筛中从2i开始标记，而非ii
   • 线性筛中缺少if (i % primes[j] == 0) break判断

3. 内存优化技巧

   • 使用bitset代替vector 节省空间
   • 分段筛法处理极大范围（1e12以上）

// 使用bitset的埃氏筛实现 bitset<10000001> is_prime; void sieve_bitset() { is_prime.set(); is_prime[0] = is_prime[1] = 0; for (int i = 2; i * i <= 10000000; ++i) { if (is_prime[i]) { for (int j = i * i; j <= 10000000; j += i) { is_prime[j] = 0; } } } }

4.3 算法扩展应用

1. 质因数分解加速
   • 预处理最小质因数表（线性筛的优势）
   • 分解时间复杂度降为O(log n)

// 预处理最小质因数表 vector<int> min_prime; void init_min_prime(int n) { min_prime.resize(n + 1); for (int i = 2; i <= n; ++i) { if (min_prime[i] == 0) { min_prime[i] = i; for (int j = 2 * i; j <= n; j += i) { if (min_prime[j] == 0) min_prime[j] = i; } } } } // 快速质因数分解 vector<int> factorize(int x) { vector<int> factors; while (x > 1) { int p = min_prime[x]; while (x % p == 0) { factors.push_back(p); x /= p; } } return factors; }

2. 区间质数筛法
   • 处理[a,b]区间内的质数（a,b可能很大，但b-a较小）
   • 结合埃氏筛思想和预处理小质数

vector<bool> segment_sieve(long long a, long long b) { vector<bool> is_prime(b - a + 1, true); if (a == 1) is_prime[0] = false; for (long long p = 2; p * p <= b; ++p) { for (long long j = max(p * p, (a + p - 1) / p * p); j <= b; j += p) { is_prime[j - a] = false; } } return is_prime; }

在算法竞赛中，质数处理既是基础也是常考点。掌握这三种筛法及其变种，能让你在面对相关问题时游刃有余。根据我的参赛经验，在时间紧迫的比赛环境中，埃氏筛法往往是性价比最高的选择，除非题目数据规模特别大或有特殊要求。