质数筛选

欧拉筛：

欧拉（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 }