质数筛（朴素、埃氏、欧拉）
介绍
作为和数学高度结合的一门学科，程序设计中经常会用到数学上的性质和概念，或者说，计算机一开始就是为了解决数学问题而发明的。在做题的过程中，我们经常遇到质数相关的题目，那么，我们如何判断一个数是不是质数呢？如何把质数全部打入表中呢？今天，我将介绍三种常见的筛取质数的方法。
朴素筛
代码实现
int main()
{
int n, c, N = 0, prime[10000];//质数数组
scanf("%d", &n);
for (int i = 2; i <= n; i++)//检测i是否为质数
{
c = 1;
for (int j = 2; j * j <= i + 1; j++)//测试i是否能被j整除
if (i % j == 0 && i != 2)
{
c = 0;
break;
}
if(c) prime[N++] = i;//填入并计数
}
for (int i = 0; i < N; i++) printf("%d ", prime[i]);
return 0;
}分析
根据质数的定义，质数有且只有两个因数，即1和它本身。
朴素筛就根据这最基本的性质，从2开始遍历，直到它的平方根，依次取余，如果整除了就违反了质数有且只有两个因数的性质，可以将其排除。
之所以只需要遍历到平方根，是因为整除时，结果也是它的一个因数，故只需要遍历到平方根，便可以将所有可能是因数的数试到。
for (int i = 2; i <= n; i++)//检测i是否为质数
{
c = 1;
for (int j = 2; j * j <= i; j++)//测试i是否能被j整除
if (i % j == 0 && i != 2)
{
c = 0;
break;
}
if(c) prime[N++] = i;//填入并计数
}这里是朴素筛的核心部分。
值得注意的是，for循环的跳出条件设置为j*j<=i，避免了sqrt函数的使用，可以显著提升运行速度。
而变量c的设置则是为了标识i是否是质数，若是因为判断为合数而跳出，则将c赋为0，后续不做处理，反之，将其存入数组。
补充
整个算法的时间复杂度为O(nlogn)。很显然，这个算法是最基础的暴力遍历，如果题目给的数据大一点就会被T得很惨，比赛时间充裕的情况尽量不要用朴素筛，就跟尽量用快排别用冒泡一个道理。
埃氏筛
代码实现
#include<stdio.h>
#include<stdbool.h>
#define maxNum 1000000001//定义最大值
bool priNum[maxNum];//质数为真，否则为假
void savePriNum()//创建预处理质数集
{
for (int i = 0; i < maxNum; i++)
priNum[i] = true;//默认真
priNum[0] =priNum[1] = false;
for (int i = 2; i * i < maxNum ; i++)//依次筛掉i的倍数，不包括i
for (int j = 2 * i; j < maxNum; j += i)
priNum[j] = false;
}
int main()
{
savePriNum();
int n;
scanf("%d", &n);
for (int i = 2; i <= n; i++)
if (priNum[i])
printf("%d\n", i);
return 0;
}分析
质数有且只有两个因数，那也就是说，任何数的倍数都不可能是质数，那我们只需要在遍历2到它的平方根，并标记这些数在要求范围内的倍数为合数，那剩下的数就是质数了。
#include<stdbool.h>
#define maxNum 1000000001//定义最大值
bool priNum[maxNum];//质数为真，否则为假首先，我们先创建一个布尔型数组来存放质数。因为数据范围极大，而我们只需要存放0和1来标记质数合数，所以我们采用值只有true和false的布尔型变量，来节省空间。
void savePriNum()//创建预处理质数集
{
for (int i = 0; i < maxNum; i++)
priNum[i] = true;//默认真
priNum[0] =priNum[1] = false;
for (int i = 2; i * i < maxNum ; i++)//依次筛掉i的倍数，不包括i
for (int j = 2 * i; j < maxNum; j += i)
priNum[j] = false;
}我们将存表操作封装进函数中。
首先，我们默认每个数都为质数，接着，特判0和1不是质数，同时，0和1也不在我们遍历的过程中。
我们从2开始，遍历到范围最大值的平方根，标记这些数在要求范围内的倍数为合数。
这样，我们想判断x是不是质数，只需要查询priNum[x]的值就可以了。
补充
整个算法的时间复杂度为O(nloglogn)，已经很逼近线性时间O(n)了，但是我们可以发现，埃氏筛在标记合数时，是有重复标记的。当一个合数拥有多个因数时，就会被标记多次，例如12拥有因数1，2，3，4，6，12，除去1和12，在遍历2，3，4，6时，12都被标记了一次，所以，埃氏筛还并不是线性时间。
欧拉筛
代码实现
#include<stdio.h>
#include<stdbool.h>
#define maxNum 1000000001//定义最大值
bool priNum[maxNum];//质数为真，否则为假
int pri[maxNum], N = 0;
void savePriNum()//创建预处理质数集
{
for (int i = 0; i < maxNum; i++)
priNum[i] = true;//全部填入真
priNum[0] = priNum[1] = false;
for (int i = 2; i <= maxNum / 2; i++)
if (priNum[i])
{
pri[N] = i;//存入数组并计数
N++;
for (int j = 0; j < N; j++)//若i为质数，则标记它和其他质数的每一个乘积
if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;
else break;//
}
else
for (int j = 0; j < N; j++)
{
if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;//若i为合数，则标记它和其他质数的乘积
if (i % pri[j] == 0) break;//直到i整除到某质数
}
return 0;
}
int main()
{
savePriNum();
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
if (priNum[i])
printf("%d ", i);
return 0;
}分析
欧拉筛又称线性筛，在欧拉筛中每个合数都只会被标记一次，因此，算法的时间是线性的，时间复杂度到了O(n)。
为了实现每个合数只被标记一次，在欧拉筛中我们规定每个合数都只会被它的最小因数标记，这里的意思是通过该数最小因数*某数=该数来标记该数。
#include<stdio.h>
#include<stdbool.h>
#define maxNum 1000000001//定义最大值
bool priNum[maxNum];//质数为真，否则为假
int pri[maxNum], N = 0;预处理时，我们另外创建一个数组，用于即时存放筛选出的质数，同时设置变量N用于记录当前质数数量。
void savePriNum()//创建预处理质数集
{
for (int i = 0; i < maxNum; i++)
priNum[i] = true;//全部填入真
priNum[0] = priNum[1] = false;
for (int i = 2; i <= maxNum / 2; i++)
;//......
return 0;
}我们同样将存表操作封装进函数中，默认存真，特判01，不做赘述。
但遍历需要遍历至最大值的一半，因为最大值需要被它的最小因数标记，这个最小因数可能是2，那就需要遍历到它的二分之一。
if (priNum[i])
{
pri[N] = i;//存入数组并计数
N++;
for (int j = 0; j < N; j++)//若i为质数，则标记它和其他质数的每一个乘积
if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;
else break;//
}当我们遍历到一个质数时，我们将其存入质数数组并计数，然后将其与已经存入的质数相乘，并标记相乘的积为合数。
两个不同质数相乘的积有且只有4个因数，两个相同质数相乘的积有且只有3个因数，这是分解质因数的原理。
也因此，我们通过此法标记的数，必然是通过它的最小因数来标记的。
else
for (int j = 0; j < N; j++)
{
if (pri[j] * i < maxNum) priNum[pri[j] * i] = false;//若i为合数，则标记它和其他质数的乘积
if (i % pri[j] == 0) break;//直到i整除到某质数
}而当我们遍历到一个合数时，我们同样将其与已经存入的质数相乘，并标记相乘的积为合数。
但欧拉筛的精髓之处来了。
当该数在相乘中遍历到自己的一个因数后，就需要break跳出，终止循环。
同样以12举例，当i遍历到4，j遍历到2时，4%2==0，此时需要跳出，j不能继续遍历到3，若通过4*3=12来标记12，在i遍历到6时，6*2=12便会重复遍历，也违反了合数需要被自己的最小因子标记的规则。
总结
朴素筛和埃氏筛的实现原理是比较简单的，使用的场景也比较广泛，但在个别的竞赛题中会T，必须使用欧拉筛。
欧拉筛理解的过程是有点难的，但在真正理解之后思路会非常清晰，主要就是合数需要被自己的最小因子标记的规则，需要细细体会。
以上便是质数筛三种筛法的介绍，本文由凉茶coltea撰写，转载请注明出处。