C语⾔⼁筛法求素数（质数）
素数（质数）是指在⼤于1的⾃然数中，除了1和它本⾝以外不再有其他因数的⾃然数。素数被⼴泛⽤于密码学、汽车变速箱齿轮设计、害⾍的⽣物⽣长周期与杀⾍剂使⽤之间的关系、导弹和等领域上，具有重要意义。本⽂就来介绍求素数的⼀种⽅法：筛法。
在初学编程时，我们解决问题的想法应该都是定义法。按照素数的定义——除了1和它本⾝以外不再有其他因数的⼤于1的⾃然数，我们可以这样判断⼀个整数x是否为素数：
⾸先，x(x>1)满⾜不能被1和x以外的其他数整除，即我们可以遍历2~x-1，看是否有整数能整除x，这种⽅法称为试商法。为此我们可以写出最初版的代码：
int IsPrime(int x)
{
int i, flag = 1;
if (x <= 1)//若x<=1，则不是素数
flag = 0;
for (i=2; i<x && flag; i++)
{
if (x%i == 0)//若x能被2~x-1中的整数整除，则不是素数
flag = 0;
}
return flag;//若是素数则返回1，否则返回0
}
但是当x较⼤时，循环的次数较多，效率低下。实际上，只要在2~x-1中发现了任意⼀个整数能够整除x，则可⽴刻判断x不是素数，此时已经可以跳出循环，不再进⾏重复⽆意义的⼯作，即：
int IsPrime(int x)
{
int i, flag = 1;
if (x <= 1)//若x<=1，则不是素数
flag = 0;
for (i=2; i<x && flag; i++)
{
if (x%i == 0)//若x能被2~x-1中的整数整除，则不是素数
{
flag = 0;
break;//只要到第⼀个，即可跳出循环
}
}
return flag;//若是素数则返回1，否则返回0
}
实际上，只需⽤2~sqrt(x)之间的整数去试商看是否能被整除即可（这⾥不给出数学证明，有兴趣的朋友可以⾃⾏查阅资料），为此我们可以把循环条件改为i<=sqrt(x)，此时若x不是素数，循环次数将⼤⼤减少，可以进⼀步改进我们的代码。
int IsPrime(int x)
{
int i, flag = 1;c++判断素数
int squareRoot = sqrt(x);
if (x <= 1)//若x<=1，则不是素数
flag = 0;
for (i=2; i<=squareRoot && flag; i++)
{
if (x%i == 0)//若x能被2~sqrt(x)中的整数整除，则不是素数
{
flag = 0;
break;//只要到第⼀个，即可跳出循环
}
}
return flag;//若是素数则返回1，否则返回0
}
若我们要实现求100以内的所有素数，可在主函数中调⽤IsPrime()函数如下：
int main()
{
int i;
for (i=1; i<=100; i++)
{
if (IsPrime(i))
printf("%d\n", i);
}
return 0;
}
但是试想，如果我们要实现求素数的范围较⼤（如100000以内），那么在遍历1~100000的循环中，每⼀次循环都要调⽤⼀次IsPrime()函数，且在函数中还要遍历2~sqrt(i)，这样将会使程序的效率变得异常低下。事实上，我们完全可以出较少的数（范围
为2~sqrt(100000)）后，把这些数的倍数全部筛掉，这样就省去了很多的判断步骤，这种⽅法称为筛法。
这其实就是试商法中的算法原理：若2~sqrt(x)中有整数能够整除x，那么x⼀定不是素数，也就是若x不是素数，则⼀定存在某个数位于2~sqrt(x)中（记为i），x是i的倍数。
那么如何实现这个算法呢？我们可以考虑⽤⼀个数组a来存储1~N中的所有数，并先把0与1筛去，即初始化数组a，使a[0]=0, a[1]=0,
a[2]=2, a[3]=3, ......, a[N]=N；接着对i=2, 3, ......, sqrt(N)分别做：“筛掉a中的所有a[i]的倍数”，即当i+1<=j<=N时，若a[j]是a[i]的倍数，使a[j]=0；最后输出数组中余下的数（a[i]!=0的数）。
据此，我们可编写代码如下：
for (i=2; i<=N; i++)
{
a[i] = i;//初始化a[2]~a[N]
}
for (i=2; i<=sqrt(N); i++)
{
if (a[i]!=0)//跳过已被筛掉的数
{
for (j=i+1; j<=N; j++)
{
if (a[j]!=0 && a[j]%a[i]==0)//a[j]!=0的⽬的是跳过已经被筛掉的数
{
a[j] = 0;
}
}
}
}
for (i=0; i<N; i++)
{
if (a[i])//如果a[i]!=0，则a[i]是素数
{
printf("%d\n", a[i]);
}
}
⽽在这种⽅法中，我们发现，当输出素数时，既可以输出i，也可以输出a[i]，那么就说明了有⼀个值是多余的。其实，我们完全可以使⽤a[i]当作标记变量，在⼀开始时把数组a初始化为0，让j遍历2~N，当我们到⾮素数则使a[j]变为1，代表筛掉了⾮素数，最后只需输出元素a[j]=0的下标j即可。据此我们可以优化以上代码：
int i, j, a[N+1] = {0};//假设N为常量
a[0] = 1;
a[1] = 1;//0和1不是素数
for (i=2; i<=sqrt(N); i++)
{
if (a[i]!=1)//跳过已被筛掉的数
{
for (j=i+1; j<=N; j++)
{
if (a[j]!=1 && j%i==0)//a[j]!=1的⽬的是跳过已经被筛掉的数
{
a[j] = 1;
}
}
}
}
for (i=0; i<N; i++)
{
if (!a[i])//如果a[i]==0，则a[i]是素数
{
printf("%d\n", i);
}
}
这样我们就可以省去把数组a初始化为a[2]=2,......,a[N]=N的⼀步了，从⽽减少了⼀个循环，提⾼了程序运⾏的效率。
在这⾥，我们判断j是否为i的倍数时，采⽤的时让j从i+1遍历到N，判断j对i求余是否为0的⽅法。这样做其实也是不必要的，因为相⽐于i的倍数来说，不是i的倍数的数要多得多。因此我们可以让j从2开始，直到i*j>N，这样我们就能直接到i的倍数i*j，并让a[i*j]=1。
a[0] = 1;
a[1] = 1;//0和1不是素数
for (i=2; i<=sqrt(N); i++)
{
if (a[i]!=1)//跳过已被筛掉的数
{
j = 2;
while (i*j<=N)
{
a[i*j] = 1;
j++;
}
}
}
for (i=0; i<N; i++)
{
if (!a[i])//如果a[i]==0，则a[i]是素数
{
printf("%d\n", i);
}
}
这就是代码经优化的最终版本啦！
筛法求素数的核⼼是依次筛掉2~sqrt(N)中素数的倍数，直到a中仅剩下素数为⽌，这种⽅法巧⽤数组，利⽤数组作为标志变量，是⼀种效率较⾼的求素数的算法。
参考⽂献：
[1]百度百科.