源自项目：2020贵软自无转系面试题参考答案
其中有个面试题，问如何求1~1000以内的素数，由于数据规模小，可以用“土办法”。但如果把1000改为更大的数，就需要用到素数筛了。参考回答如下。后附实现代码。
埃氏筛
可以用埃氏筛的方式。先开一个长度为N+1的布尔型数组，数组的下标对应N以内的数，先把数组初始化为全0，意味着是素数。接下来，从i=2开始遍历这些数，如果它的布尔标记为0，那么就把它的2倍、它的3倍、……一直到N以内最大的它的整数倍为止，将这些数都标记为1，意思是不是素数。如果i已经被标记为1，那么就直接跳过即可。最后N以内的素数就是标记仍然为0的数。（0、1除外。）时间复杂度为O(n*log(log(n)))。
（改进版：）
可以用埃氏筛的方式。先开一个长度为N+1的布尔型数组，数组的下标对应N以内的数，先把数组初始化为全0，意味着是素数。接下来，从i=2开始遍历这些数，如果它的布尔标记为0，那么从j=i*i开始，每次j递增i，将j对应的数都标记为1，意思是不是素数，直到j大于N。如果i已经被标记为1，那么就直接跳过即可。最后N以内的素数就是标记仍然为0的数。（0、1除外。）时间复杂度为O(n*log(log(n)))。
（大佬们可以继续前进！如果问你不是1000而是300000000呢？）
欧拉筛
可以采用欧拉线性筛的方式。开两个长度为(N+1)的数组，一个为bool型，初始化为0，用于标记是否是素数；另一个int型，名为prime，初始化为全0，用于存储已经找到的素数。从i=2开始，我们用外层循环遍历每一个数，如果i的标记是0，那么把i添加进记录素数的数组中；然后无论i的标记，开启内层循环，令j=0，开始遍历prime中存的每一个素数prime[j]，将i*prime[j]都标记为1。一直循环到某次i%prime[j]等于0，终止内层循环，继续外层循环，直至i>N结束外层循环。最后N以内的素数就是保存在prime数组中前面的非零数。
本算法时间复杂度为O(n)，因此称为线性筛。其中优化的原理在于每个合数都只被它最小的质因子筛去，减少了不必要的重复。
欧拉筛的关键代码是
if (i % primes[j] == 0) // most important
break;它的目的是保证每个合数都只被它最小的质因子筛去。
比如，i=15时，会依次筛掉i*primes[0]=15*2=30，和i*primes[1]=15*3=45。而此时i%primes[1]=15%3=0，因此会break，于是i*primes[2]=15*5=75就不会在i=15时筛掉；75会被它最小的质因子3筛掉，也就是i=25时，被i*primes[1]=25*3=75筛掉。
为什么呢？简单来说，当i%primes[j]=0时，i有质因子primes[j]。接下来是准备用primes[j+1]筛掉i*primes[j+1]；而由于i有质因子primes[j]，i*primes[j+1]就有质因子primes[j]；同时，i*primes[j+1]有质因子primes[j+1]，且primes[j]<primes[j+1]。因此如果用primes[j+1]筛掉i*primes[j+1]，而不是用primes[j]筛掉i*primes[j+1]，就不满足“保证每个合数都只被它最小的质因子筛去”了。因此当i%primes[j]=0时就需要break。
以上内容的严谨证明请参阅参考资料。
实现
改进版埃氏筛：
// Created by Colin on 2020/05/17.
// Copyright © 2020 Colin. All rights reserved.
// https://blog.valderfield.com/archives/35/
#include <iostream>
using namespace std;
void E_sieve(const int N, bool* not_prime)
{
not_prime[0] = not_prime[1] = 1;
for (int i = 2; i <= N; i++)
{
if (!not_prime[i])
{
auto j = (long long)i * i; // j may exceed int !!!
if (j <= N)
for (; j <= N; j += i)
not_prime[j] = 1;
}
}
}
int main()
{
bool not_prime[1000001] = { 0 };
int n;
cin >> n;
E_sieve(n, not_prime);
for (int i = 2; i <= n; i++)
{
if (!not_prime[i])
cout << i << ' ';
}
cout << endl;
return 0;
}欧拉筛：
// Created by Colin on 2020/05/17.
// Copyright © 2020 Colin. All rights reserved.
// https://blog.valderfield.com/archives/35/
#include <iostream>
#include <vector>
using namespace std;
void Euler_sieve(const int N, vector<int>& primes)
{
bool not_prime[1000001] = { 0 };
not_prime[0] = not_prime[1] = 1;
for (int i = 2; i <= N; i++)
{
if (!not_prime[i])
primes.push_back(i);
for (int j = 0; j < primes.size() && i * primes[j] <= N; j++)
{
not_prime[i * primes[j]] = 1;
if (i % primes[j] == 0) // most important
break;
}
}
}
int main()
{
int n;
cin >> n;
vector<int> primes;
Euler_sieve(n, primes);
for (auto x : primes) // supported by C++11
cout << x << ' ';
cout << endl;
return 0;
}参考资料：
OI Wiki - 筛法（利益无关，友情安利。）