埃氏筛算法：高效质数筛选原理与实现

1. 埃氏筛算法概述

埃拉托斯特尼筛法（简称埃氏筛）是一种古老而高效的质数筛选算法，由古希腊数学家埃拉托斯特尼在公元前3世纪提出。这个算法的精妙之处在于它通过简单的标记操作就能快速找出一定范围内的所有质数，时间复杂度为O(n log log n)，远优于逐个判断的O(n√n)方法。

质数筛选在编程竞赛和实际开发中都非常重要。比如在密码学中需要生成大质数，在算法题中经常需要预处理质数表。埃氏筛特别适合处理1e5到1e7范围内的质数筛选，这也是蓝桥杯等编程竞赛的常见数据规模。

提示：虽然埃氏筛不是最快的质数筛法（线性筛更快），但它实现简单、容易理解，是算法入门的最佳选择。

2. 算法核心原理

2.1 基本思想

埃氏筛的核心思想可以用"排除法"来理解：

1. 假设所有大于等于2的数都是质数
2. 从最小的质数2开始，将其所有倍数标记为非质数
3. 移动到下一个未被标记的数，重复步骤2
4. 最终未被标记的数就是质数

这个过程就像筛子一样，把合数一点点"筛掉"，剩下的就是质数。

2.2 数学基础

算法的正确性基于以下数论原理：

• 任何合数都可以表示为质数的乘积
• 因此，所有合数都至少有一个不大于其平方根的质因数
• 这意味着我们只需要用不超过√n的质数去筛，就能确保所有合数都被筛掉

2.3 关键优化点

原始算法可以从i×2开始标记，但有两个重要优化：

1. 从i×i开始标记：因为对于任何k×i（k < i），这个数已经被更小的质数k筛过了。比如当i=5时，5×2=10已经被i=2筛过，5×3=15已经被i=3筛过，所以直接从5×5=25开始标记即可。

2. 外层循环只需到√n：因为任何大于√n的数的倍数都会超过n，不需要再处理。例如筛选100以内的质数，只需要用2到10的质数筛即可。

3. 完整实现与详细解析

3.1 数据结构设计

我们使用两个核心数据结构：

1. bool is_prime[MAX_N]：标记数组，is_prime[i]为true表示i是质数
2. vector<int> prime：存储筛选出的所有质数

cpp复制const int MAX_N = 100005;  // 筛选范围上限
vector<int> prime;