1. 引言
质数在数学中有着重要的地位，其定义为只能被1和本身整除的自然数，如2、3、5、7等。获取小于一个给定数n的所有质数是一个经典问题，也是许多算法和编程语言的基本练习之一。本文将介绍一种有趣的解决方案，即埃氏筛法，来获取小于n的所有质数。
2. 埃氏筛法
埃氏筛法，也叫素数筛法，是一种简单有效的求解素数的方法。它的基本思想是从2开始，将每个质数的倍数都标记成合数，直到没有未标记的数为止。因为一个数如果有小于它的质因子，那么在处理到这个质因子时，这个数已经被标记过了。
2.1 基本流程
具体地，埃氏筛法的基本流程如下：
从2开始，将小于n的每个数都标记为质数（初始状态下都是质数）；
将2的倍数（除2以外，2的倍数肯定不是质数）标记为合数；
将下一个未标记的数3作为新的质数，将3的倍数标记为合数；
将下一个未标记的数5作为新的质数，将5的倍数标记为合数；
重复步骤3和4，直到无法找到下一个未标记的数。
经过以上步骤，剩下的未标记的数都是质数，即可得到小于n的所有质数。
2.2 优化
埃氏筛法的时间复杂度为O(nloglogn)，虽然已经很不错了，但在处理极大的n值时仍会有较大的性能瓶颈。因此，我们可以从以下几个方面进行优化：
只需筛选到sqrt(n)即可（当p>sqrt(n)时，p*p>n）；
对于每个质数p，从p*p开始标记（所有小于p*p的倍数，在之前已被筛选掉了）；
使用bool数组代替int数组，降低空间复杂度。
3. C++代码实现
参考以下C++代码实现，其中使用了以上优化方法：
const int N = 1e7+10;
bool prime[N];
vector<int> get_primes(int n) {
vector<int> primes;
memset(prime, true, sizeof(prime));
prime[0] = prime[1] = false;
for (int i=2; i<=sqrt(n); ++i) {
if (prime[i]) {
for (int j=i*i; j<=n; j+=i) {
prime[j] = false;
}
}
}
for (int i=2; i<=n; ++i) {
if (prime[i]) {
primes.push_back(i);
}
}
return primes;
}
这个函数返回小于n的所有质数，返回类型为vector<int>，可以轻松地遍历结果。
4. 总结
埃氏筛法是一种简单有效的获取小于n的所有质数的算法，其时间复杂度为O(nloglogn)。在处理极大的n时，可以采取优化措施，降低时间和空间复杂度。