筛法求2～1000之间的所有素数

筛法求2～1000之间的所有素数2011-03-29筛法求素数首先要建立筛子，这里利用数组作筛子。下标对应于数，相应下标变量的值标志是否在筛子中：为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（"
"）;／*5个素数输出在一行*／
}

}