欧拉筛：
欧拉（Euler）筛法是用于找到从1 11开始，到给定的最大数之间的所有质数的一种筛法，其时间复杂度是O ( n ) O(n)O(n)。其中欧拉筛法有效地避免了埃拉托斯特尼（Eratosthenes）筛法中重复的筛选，保证了每个数只筛选一次，成功地降低了时间复杂度。
一、埃拉托斯特尼（Eratosthenes）筛法
埃拉托斯特尼（Eratosthenes）筛法是要得到自然数n nn以内的全部质数，必须把不大于n \sqrt{n}
n
的所有质数的倍数剔除，剩下的就是质数。
这是因为如果是n nn合数，那么它一定有一个不大于n \sqrt{n}
n
的质因子，所以过了n \sqrt{n}
n
就不用再更新了。
具体算法为：
遍历，将质数记录在数组中；
如果是质数的话，将所有这个数的倍数记录为合数；
对 到 进行遍历，是质数就加入数组中。
代码：
1 const int MAXN = 10000;
2
3 int cnt; //记录总共有多少个质数
4 int Prime[MAXN]; //记录所有质数
5 int NotPrime[MAXN]; //打标记
6
7 void Eratosthenes_Prime(int n)
8 {
9 cnt = 0;
10 memset(Prime, 0, sizeof(Prime));
11 memset(NotPrime, 0, sizeof(NotPrime));
12 for (int i = 2; i <= (int)sqrt(n + 0.5); ++i)
13 {
14 /*如果是质数，则记录下来*/
15 if (!NotPrime[i])
16 Prime[cnt++] = i;
17
18 /*将后面质数i的倍数都记录成合数*/
19 for (int j = 2; i * j <= n; ++j)
20 NotPrime[i * j] = 1;
21 }
22
23 /*后面的用前面的质数已经筛完，直接记录*/
24 for (int i = (int)sqrt(n + 0.5) + 1; i <= n; ++i)
25 if (!NotPrime[i])
26 Prime[cnt++] = i;
27 }