素数筛选法（埃拉托斯特尼方法）的代码实现

首先，我们应当先复习一下原始的筛选法原理，先圈出2，并且划掉列表中2的倍数（即其他偶数），然后回到开始，圈出第一个没有被画掉的数，画掉剩下数表中他的所有倍数。重复这一过程足够多次数，剩下的没有被画掉的就是我们要寻找的素数。并且，不难推出，我们要在所圈到的不小于sqrt（n）的最大整数之前就要停止筛选，这时候就不用再去找接下来的素数，只需要将没有画掉的数字画上即可。这便是原始的筛选法。

其次，对于代码的实现，我们不妨可以对原先筛选法做出一些修改，使其更容易，也更好被人理解地促成代码实现。原始的方法里面是要找到一个素数就要划掉他的所有倍数，明显，这是很难用代码实现的，我们可以这样子做：提前设置一组足够长度的数组，我们用这个数组来储存已经找到的素数，并且，我们利用循环，使得循环一开头数组对应项都能被塞入最新找到的素数，然后及时输出，每轮最后在使得循环变量更新，在中间，我们再放一个循环，用于检测到剩下的数里面第一个能找到的素数，然后马上就赋值给循环变量，这样代码整体就能实现正确的素数输出。额外的，为了减少工作量，前面的找到的素数，我们可以使其含义变为需要用于筛选的最小素数列，并且在循环末端进行判断，如果刚刚好，其实就不用再让数组继续储存新素数了。

代码实现：

#include

#include

int main()

{

   int N;scanf("%d",&N);

   int m=floor(sqrt(N));

   int a[m];

   int i=2,j=0;

   while(i<=N){

       a[j]=i;

       printf("%d\n",i);

       if(i==N)break;

       int k=i+1,ctt=0;

       for(k=i+1;k<=N;k++){

           int temp=0;ctt=0;

           for(temp=0;temp<=j;temp++){

               if(k%a[temp]!=0)ctt++;

           }

           if(ctt==j+1)break;

       }

       if(ctt!=j+1)break;

       i=k;

       if(m>=k)j++;

   }

   return 0;

}

优化过的形式：

谢谢阅

#include<stdio.h>

#include<math.h>

int main()

{

   int N;scanf("%d",&N);

   int m=floor(sqrt(N));

   int a[m];

   int i=2,j=0;

   while(i<=N){

       static int sign=0;

       if(sign==0)a[j]=i;

       printf("%d\n",i);

       if(i==N)break;

       int k=i+1,ctt=0;

       for(k=i+1;k<=N;k++){

           int temp=0;ctt=0;

           for(temp=0;temp<=j;temp++){

               if(k%a[temp]!=0)ctt++;

           }

           if(ctt==j+1)break;

       }

       if(ctt!=j+1)break;

       i=k;

       if(m>=i) j++;

       else sign=1;

   }

   return 0;

}

谢谢阅读！