Question

C语言问题：用筛选法求100之内的素数。（利用数组。）

如果能详细解释一下就更好了。

Answer 1

/*
素数是只能被1和本身整除的数，1除外
*/
#include <stdio.h>

// 用MAXNUMBER表示100，方便以后程序的修改
#define MAXNUMBER 100

void GetPrime();
int main()
{
GetPrime();
return 0;
}

void GetPrime()
{
int startNumber = 2, i;
// 从2开始到MAXNUMBER结束，一个个测试
for(startNumber = 2; startNumber <= MAXNUMBER; startNumber++)
{
// 2比较特殊，所以要单独处理
if(startNumber == 2)
{
printf("%5d", startNumber);
continue;
}
// 从2开始到startNumber结束，用startNumber去对i求模
// 如果startNumber%i==0 表示startNumber不是素数，因为它能被i整除
for(i = 2; i < startNumber; i++)
{
// 如果startNumber能被小鱼startNumber内的数整除
// 表示startNumber不是素数
if(startNumber % i == 0)
{
// 跳出for循环
break;
}
}
// 跳出for循环后判断这个数是不是素数
// 如果i>=startNumber表示这个for循环不是通过break跳出的
// 而是执行到i=startNumber，即i<startNumber为假时跳出的循环
// 这样的startNumber即为素数。
if(i >= startNumber)
{
printf("%5d", startNumber);
}
}
printf("\n");
}

/*
求素数有很多方法，这个只是入门级别的方法。
*/

Answer 2

//埃拉托色尼筛,算法设计与分析基础,第5页
#include<stdio.h>
#include<math.h>
#define N 100
int main(){
int a[N];
int i, j, temp;
for(i=2; i<N; i++)
a[i]=i;
a[1]=0;
temp=(int)floor(sqrt(N-1));
for(i=2; i<=temp; i++){
if(a[i]!=0){
j=a[i]*a[i];
while(j<N){
a[j]=0;
j+=i;
}
}
}
for(i=0; i<N; i++){
if(a[i]!=0)
printf("%2d ", a[i]);
}
putchar('\n');
return 0;
}