筛选法又称筛法，具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。因为希腊人是把数写在涂蜡的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。）

要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。

实现一

1.抽象步骤

<1>先将1去掉

<2>将2的倍数去掉。

<3>将3的倍数去掉。

……

<i>将i的倍数去掉。

……

一直到A。

2.具体化

以数组array为例，其中array=n+1;

循环开始

<1> 判断array的值。

array的值是1；不执行操作

<2> 判断array的值。

array的值是2；

用array去除它后面的array、array、array……array；

能被array整除的，例如array（值为4）、array（值为6），全部置1；

即：if (array%array==0) array=1;

i=2,3,4……n

<3> 判断判断array的值。

array的值是3；

用array去除它后面的各数，把array的倍数全部置1。

比如array（值为9），array（值为15），全部置为"1"。

即：if (array%array==0) array=1;

i=3,4,5……n

<4> 判断array的值。

array原本的值为4，但是经过步骤<2>，现array的值为1；

换句话说，如果array的值为1，那么它一定可以被 array 和 array 中的某一个整除。

所以array曾经是合数，不执行操作。

………………………

<i> 判断array的值。

如果 array==1，那么array一定可以被array、array、……array中的某一个数整除

所以曾经的array是合数，不执行任何操作。

否则 array!=1，那么array是素数。

用array去除array、array、……array。

能被array整除的各项，全部置1。

………………………

<n> 判断array的值。

如果 array==1，那么array一定可以被array~array中的一项整除。

所以array是合数，不执行任何操作。

如果 array！=1，那么array~array都不能将它整除。

所以 array是素数。

循环结束。

经过以上循环，所有合数都被置“1”，输出所有非“1”的array

即if（array！=1） printf("%d",array);

程序结束。

3.代码实现

#include<cstdio> int main(int argc, char const *argv) {     //if it is prime ,it's 0     bool prime;     for (int i = 0; i < 1000; ++i)     {         prime=0;         }     prime=1;     prime=1;     for(int i=2;i<1000;i++){         if(prime==0){             for(int j=i*2;j<1000;j+=i)                 prime=1;         }     }     for (int i = 0; i < 1000; ++i)     {         if(prime==0)printf("%d ",i );     }     return 0; }

实现二

#include<stdio.h> void main() {     int i;     int N,count,p=0;     int r;//限制数据量大小为1000      printf("你想求多少以内的素数:");      scanf("%d",&N);     for(i=1;i<=N;i++)//为方便计，从1起     r=1;     count=2;//筛选起点为2     while(count<=N/2) //显然：count不会超过N/2,必能使留下的数全为素数。     {         for(i=count+1;i<=N;i++)         {             if(r==1&&i%count==0)             r=0;         }         for(i=count+1;i<=N;i++)         {             if(r==1)             {                 count=i;                 break;             }         }     }      printf("%d以内的素数为:\n",N);     for(i=2;i<=N;i++)     if(r==1)     {         p++;          printf("%d ",i);         if(p%10==0)//增设p为输出换行         printf("\n");     }     printf("\n"); } ----------------------纯粹按“筛选法”原理实现--------------------------

实现三

此筛选法遵循了C程序模块化的习惯，将筛选法独立为一个函数在主函数里调用，此代码在VC6.0中完全可以直接使用。

#include"stdio.h" #include"string.h" int a;        //定义一个容器 int n,i,j,k,count=0,temp,cs=1; int SXF(int n)        //筛选法，n为范围 {     for(i=0;i<n;i++)        //在定义的范围内循环     {         if(a<=1)            //判断当前数组存放数值是否大于1             continue;        //为真，结束本次循环         temp=2*a;        //为假，temp赋值为当前数值的两倍          while(temp<n)        //temp不能超过范围         {             a=1;        //将通过的数值的倍数全部赋值为1             temp=temp+a;         }     }     return 0; } void main() {     for(j=0;j<10000;j++)        //容器赋值     {         a=j;     }      printf("请输入你要查找素数的范围（1~10000）：");      scanf("%d",&n);     SXF(n);     printf("范围内的素数：\n");     for(k=0;k<n;k++)     {         if(a<=1)        //因为合数已经全部赋值为1，所以通过都是素数             continue;          printf("%d ",a);         count++;          while(count>=cs)    //以下可不加，为 杨辉三角格式排列         {              printf("\n");             count=0;             cs++;         }     }          printf("\n"); }

实现四

#include<stdio.h> int_tmain(intargc,_ TCHAR*argv) {     intnum=100;     inta;     for(inti=0;i<num;i++)     {         a=i+2;     }     for(inti=1;i<num-1;i++)        //i+1作为除数     {         for(intj=i+1;j<num;j++)        //a作为被除数         {             if(a!=0&&a%(i+1)==0)             {                 a=0;        //非素数置零             }         }                                                    for(inti=1,n=0;i<num;i++)     {         if(a!=0)         {              printf("%d\t",a);             if(++n%10==0) //十个一组输出             {                  printf("\n");             }         }     }     printf("\n");     return0;  }

实现五

primes() -> % 提取列表首尾元素     case Cur =< math:sqrt(lists:last(Upto)) of          true -> % 如果列表第一个元素小于等于输入长度              % 记录列表首个元素          ++ primes (                 % 筛去不能整除首元素的元素          ); % 递归调用自身          _ ->   % 否则，              % 返回整个列表     end. main() -> io:write(primes(lists:seq(2,10000))). % 输出 2 到 10000 的所有质数