1. 素数筛法概述

素数（质数）是指大于1的自然数中，除了1和它本身外不再有其他因数的数。寻找素数的方法统称为素数筛法，这是数论和计算机科学中的基础算法之一。在实际应用中，素数筛法被广泛用于密码学、哈希算法、随机数生成等领域。

常见的素数筛法主要有三种：试除法、埃拉托斯特尼筛法（埃氏筛）和欧拉筛（线性筛）。这三种方法各有特点，适用于不同场景：

• 试除法：最直观的方法，适合判断单个数字是否为素数
• 埃氏筛：适合批量筛选一定范围内的素数
• 欧拉筛：埃氏筛的优化版本，时间复杂度更低

在实际编程竞赛和工程应用中，掌握这三种筛法及其优化技巧至关重要。下面我们将从原理到实现，详细解析每种筛法的核心思想和优化策略。

2. 试除法：最基础的素数判断方法

2.1 基本原理与实现

试除法是最直观的素数判断方法，其核心思想是：对于一个待判断的数n，用2到√n之间的所有整数去试除n，如果都不能整除，则n为素数。

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

这个实现有几个关键点：

1. 边界条件处理：n≤1时直接返回false
2. 循环终止条件：只需检查到√n即可（用i*i<=n代替sqrt(n)计算，避免浮点运算）
3. 试除范围：从2开始，因为1不是素数也不是合数

2.2 优化策略

虽然试除法简单直观，但仍有优化空间：

1. 提前排除偶数：除了2，所有偶数都不是素数
2. 步长优化：检查完2后，只需检查奇数
3. 预先生成小素数表：对于多次判断的情况，可以预先生成小素数表

优化后的实现：

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

2.3 时间复杂度分析

试除法的时间复杂度为O(√n)，对于单个数的判断尚可接受，但当需要判断大量数字时效率较低。例如判断1到10^6的所有素数，时间复杂度约为O(n√n)=10^9，这在竞赛中通常无法通过时间限制。

提示：试除法适用于需要判断少量大数是否为素数的场景，或者作为其他筛法的辅助验证工具。

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

3.1 算法原理

埃氏筛是一种高效的批量筛选素数的方法，其基本思想是：

1. 初始化一个布尔数组isPrime[]，标记所有数为素数（true）
2. 从第一个素数2开始，标记其所有倍数为非素数（false）
3. 找到下一个未被标记的数，重复步骤2
4. 最终isPrime数组中为true的即为素数

vector<bool> sieveOfEratosthenes(int n) { vector<bool> isPrime(n+1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } return isPrime; }

3.2 关键优化点

1. 外层循环终止条件：只需遍历到√n，因为更大的数的倍数已经被更小的素数标记过
2. 内层循环起始点：从i*i开始，因为更小的倍数已经被之前的素数标记
3. 空间优化：可以使用位运算压缩存储空间

3.3 时间复杂度分析

埃氏筛的时间复杂度为O(n log log n)，这比试除法的O(n√n)有了显著提升。对于n=10^6，埃氏筛仅需约O(10^6 * 6)≈6×10^6次操作，远快于试除法。

3.4 实际应用中的问题

尽管埃氏筛已经很高效，但仍存在两个主要问题：

1. 重复标记：某些合数会被多个素数重复标记（如6会被2和3都标记）
2. 内存访问不连续：标记大范围的倍数时，内存访问模式不友好，影响缓存命中率

4. 欧拉筛（线性筛）

4.1 算法原理

欧拉筛是对埃氏筛的改进，确保每个合数只被其最小质因数标记一次，从而将时间复杂度优化到O(n)。其核心思想是：

1. 维护一个素数列表primes[]
2. 对于每个数i，用已知的素数primes[j]去标记i*primes[j]为合数
3. 当i能被primes[j]整除时终止内层循环

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

4.2 关键优化解析

欧拉筛的精髓在于if (i % primes[j] == 0) break这一行：

1. 当i是primes[j]的倍数时，i可以表示为k*primes[j]
2. 那么对于下一个素数primes[j+1]，iprimes[j+1] = kprimes[j]*primes[j+1]
3. 这个数应该在i = k*primes[j+1]时被primes[j]标记，所以现在不需要标记

这样就确保了每个合数只被其最小质因数标记一次。

4.3 性能对比

4.4 实际编码技巧

1. 内存优化：可以使用位压缩技术减少内存占用
2. 并行化：埃氏筛可以分段并行处理，而欧拉筛由于依赖关系难以并行
3. 预处理：对于固定范围的查询，可以预先生成素数表

5. 高级应用与变种

5.1 分段筛法

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

1. 先筛出√n以内的素数
2. 将大区间分成若干小段
3. 用已知的小素数去筛选每一小段

vector<int> segmentedSieve(long long L, long long R) { // 生成基础素数 int limit = sqrt(R); auto basePrimes = eulerSieve(limit); vector<bool> segment(R - L + 1, true); if (L == 1) segment[0] = false; for (int p : basePrimes) { long long start = max((long long)p * p, (L + p - 1) / p * p); for (long long j = start; j <= R; j += p) { segment[j - L] = false; } } vector<int> primes; for (long long i = L; i <= R; i++) { if (segment[i - L]) { primes.push_back(i); } } return primes; }

5.2 素数计数函数

素数计数函数π(n)表示不超过n的素数个数。可以通过筛法预处理后，使用二分查找快速回答查询：

class PrimeCounter { vector<int> primes; vector<int> prefix; public: PrimeCounter(int n) { primes = eulerSieve(n); prefix.resize(n+1); for (int p : primes) { prefix[p] = 1; } for (int i = 1; i <= n; i++) { prefix[i] += prefix[i-1]; } } int count(int n) { return prefix[n]; } };

5.3 筛法求最小质因数

欧拉筛可以稍作修改，记录每个数的最小质因数，这在质因数分解等应用中非常有用：

vector<int> minPrimeFactors(int n) { vector<int> minPrime(n+1, 0); vector<int> primes; for (int i = 2; i <= n; i++) { if (minPrime[i] == 0) { minPrime[i] = i; primes.push_back(i); } for (int p : primes) { if (p > minPrime[i] || i * p > n) break; minPrime[i * p] = p; } } return minPrime; }

6. 常见问题与调试技巧

6.1 边界条件处理

1. n的范围：注意n的上限，防止数组越界
2. 0和1的处理：明确它们不是素数
3. 整数溢出：特别是i*i可能溢出，可以使用i <= n/i比较

6.2 性能调优

1. 内存局部性：尽量顺序访问数组，提高缓存命中率
2. 循环展开：对于内层循环可以尝试手动展开
3. 编译器优化：使用-O2或-O3优化级别

6.3 典型错误

1. 重复标记：在欧拉筛中忘记break条件
2. 初始条件错误：忘记初始化0和1为非素数
3. 数组大小不足：分配n+1的空间而不是n

6.4 测试用例设计

1. 小范围测试：n=10，验证2,3,5,7
2. 边界测试：n=0,1,2
3. 性能测试：n=1e6,1e7
4. 随机测试：随机选取区间验证

7. 实际应用案例

7.1 质因数分解

利用筛法预处理最小质因数表，可以高效进行质因数分解：

vector<int> factorize(int x, const vector<int>& minPrime) { vector<int> factors; while (x > 1) { int p = minPrime[x]; factors.push_back(p); x /= p; } return factors; }

7.2 欧拉函数计算

欧拉函数φ(n)表示小于n且与n互质的数的个数，可以利用筛法预处理：

vector<int> eulerPhi(int n) { vector<int> phi(n+1); for (int i = 0; i <= n; i++) { phi[i] = i; } for (int i = 2; i <= n; i++) { if (phi[i] == i) { // i是素数 for (int j = i; j <= n; j += i) { phi[j] -= phi[j] / i; } } } return phi; }

7.3 素数间隔统计

统计相邻素数的间隔分布：

void primeGaps(int n) { auto primes = eulerSieve(n); map<int, int> gapCount; for (int i = 1; i < primes.size(); i++) { int gap = primes[i] - primes[i-1]; gapCount[gap]++; } // 输出gap分布 }

8. 不同语言的实现差异

8.1 C++实现要点

1. 使用vector 节省空间（特化实现）
2. 注意缓存友好性
3. 可以使用OpenMP并行化埃氏筛

8.2 Python实现特点

1. 使用列表推导式简化代码
2. 注意Python的慢循环问题，可以借助numpy加速
3. 生成器实现惰性求值

def eratosthenes(n): sieve = bytearray([True]) * (n+1) sieve[0] = sieve[1] = False for i in range(2, int(n**0.5)+1): if sieve[i]: sieve[i*i::i] = b'\x00' * len(sieve[i*i::i]) return [i for i, prime in enumerate(sieve) if prime]

8.3 Java实现注意事项

1. 使用BitSet节省空间
2. 注意数组初始化的性能开销
3. 可以尝试使用Stream API实现函数式风格

9. 算法竞赛中的应用技巧

1. 预处理技巧：在程序开始预处理素数表，避免多次计算
2. 快速查询：对筛法结果建立前缀和数组，支持O(1)查询
3. 问题转化：将问题转化为素数相关性质利用筛法解决
4. 模板准备：准备欧拉筛的模板代码，比赛时直接使用

10. 性能实测与对比

以下是三种筛法在n=1e7时的性能对比（C++，-O3优化，i7-9700K）：

从测试可以看出：

1. 试除法完全不适合大规模计算
2. 埃氏筛在时间和空间上比较平衡
3. 欧拉筛时间最快但内存消耗较大

在实际应用中，需要根据具体场景选择：

• 内存受限时选择埃氏筛
• 时间敏感且内存充足时选择欧拉筛
• 需要处理极大范围时选择分段筛法

11. 扩展阅读与进阶方向

1. 概率素数测试：Miller-Rabin测试，适用于极大数的概率判断
2. 数论变换：利用筛法加速数论函数计算
3. 分布式筛法：将筛法分布到多台机器上处理
4. GPU加速：利用图形处理器并行计算筛法

素数筛法的优化永无止境，每年仍有新的研究成果发表。掌握这些基础算法后，可以进一步探索更高级的算法和应用。