篩法求2～1000之間的所有素數

篩法求素數首先要建立篩子，這裡利用數組作篩子。下標對應於數，相應下標變量的值標志是否在篩子中：為1表示在篩子中，為。表示已被篩去，不在篩子中。然後找每一輪篩選種子，篩選種子是完成一輪篩選後的下一個最小的素數，初值為2。

對每一輪篩選種子，篩去其所有倍數，即相應下標變量的值賦值為O。倍數初值為篩選種子的2倍。

篩選完成，篩子中剩下的即為素數。

程序如下：

／*程序8—14，篩法求2至1000之間的所有素數*／
main()
{
int a[1000];／*篩子數組*／
int i;
int minp，double;／*minp篩選種子，double倍數*／
int n=O;／*素數個數，用於輸出格式控制*／
for(i=2;i<1000;i++)／*建立篩子*／

a[i]=1;
minp=2;／*篩選種子初始化*／
while(minp<500)／*完成整個篩選*／
{double=2*minp;／*倍數初始化*／
while(double<1000)／*完成一輪篩選*／
{a[double]=O;／*篩去當前倍數*／
double+=minp;／*計算下一個倍數*／
}
do／*計算下一輪篩選種子*／
{minp++;}
while(a[minp]==0);
}

printf("2至1000之間的所有素數如下：＼n");
for(i=2;i<1000;i++)
if(a[i]==1)
{printf("％6d"，i);
n++;
if(n％5==0)printf("\n");／*5個素數輸出在一行*／
}

}