C++实现埃氏筛算法：素数筛选与性能优化

1. 埃氏筛算法概述

埃拉托斯特尼筛法（简称埃氏筛）是一种用于筛选素数的古老算法，由古希腊数学家埃拉托斯特尼在公元前3世纪提出。这个算法的核心思想是通过逐步排除已知素数的倍数来找到所有小于给定数值的素数。

在C++编程中实现埃氏筛算法，不仅能够帮助我们理解基本的数论概念，还能锻炼数组操作和循环控制等编程基本功。对于准备参加蓝桥杯等编程竞赛的新手来说，掌握这个算法尤为重要——它经常出现在与素数相关的题目中，而且时间复杂度相对较低（O(n log log n)），适合处理中等规模的数据。

提示：虽然埃氏筛不是最高效的素数筛选算法（线性筛法更快），但它实现简单、易于理解，是学习更复杂算法的基础。

2. 算法原理与数学基础

2.1 基本数论概念

素数（质数）是指大于1的自然数中，除了1和它本身外，不能被其他自然数整除的数。理解这一点对实现埃氏筛至关重要，因为算法的核心就是基于这个定义来排除非素数。

埃氏筛利用了以下数学性质：

• 任何合数（非素数）都可以表示为素数的乘积
• 最小的素数是2，也是唯一的偶素数
• 要判断n是否为素数，只需要检查是否能被小于等于√n的素数整除

2.2 算法步骤详解

算法的执行过程可以分为以下几个步骤：

1. 初始化一个布尔数组isPrime，大小为目标范围n+1，初始时所有元素设为true
2. 将isPrime[0]和isPrime[1]设为false（0和1不是素数）
3. 从第一个素数2开始，将其所有倍数标记为非素数
4. 找到下一个未被标记为false的数（即素数），重复步骤3
5. 当处理的素数大于√n时，算法终止

这个过程的精妙之处在于，它通过从小到大的素数依次排除其倍数，确保每个合数只被其最小素因子标记一次。

3. C++实现详解

3.1 完整代码实现

cpp复制#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    fo