筛法求素数首先要建立筛子，这里利用数组作筛子。下标对应于数，相应下标变量的值标志是否在筛子中：为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个素数输出在一行*／
}
}
时间： 2024-10-03 08:44:27