在C语言中，用筛选法求100之内的素数？用多种方法求，请附带流程图，谢谢

Question

如题所述

Answer 1

所谓筛选法，就是每一次都筛去不是素数的数，比如说现在我们知道2是素数，那么4,6,8，……就全标记为非素数，现在下一个数是3,3没有被标记，所以它是素数，并且同时将6,9,12，……全部标记为非素数，再一个数是4，已经被标记过，5没被标记，于是5是素数，同时把所有5的倍数标记……
代码如下:

#include<stdio.h>

// end with -1
void findPrime(int range,int *primeArray);
// 产生一些标记，标记该处值是否为素数
void findPrimeLabel(int range,int *labelArray);

int main()
{
// 声明最大范围
int range;
// 声明一个可以容纳比较多素数的数组
int primeArray[100];
int i;
printf("Input the max range:\n");
scanf("%d",&range);
// 假设工作正常，那么primeArray所指向的就是一系列素数的指针，且最后-1结束
findPrime(range,primeArray);
for(i=0; i<100; i++)
{
if(primeArray[i]==-1)
{
break;
}
else
{
printf("%d\n",primeArray[i]);
}
}
return 0;
}

void findPrime(int range,int *primeArray)
{
// algorithm:
// 最小的素数是2
// 从之后开始，每次遇到是倍数的都删掉
int *labelArray=new int[range];
int i,j=0;
// 获得标记数组
findPrimeLabel(range,labelArray);
for(i=0; i<=range; i++)
{
// 如果标记是素数，就添加到数组中去
if(labelArray[i]==1)
{
primeArray[j]=i;
j++;
}
}
// 添加结束标识符-1
primeArray[j]=-1;
delete [] labelArray;
}

void findPrimeLabel(int range,int *labelArray)
{
int i,j=2;
labelArray[0]=0;
labelArray[1]=0;
// 初始化
for(i=2;i<=range;i++)
{
labelArray[i]=1;
}
for(i=2; i<=range; i++)
{
// 如果仍然是1，说明没被标记，则这是一个素数
if(labelArray[i]==1)
{
// 采用一个while循环，将从2开始的倍数全部标记为0
while(i*j<=range)
{
labelArray[i*j]=0;
j++;
}
j=2;
}
}
}

Answer 2

#include "stdio.h"
void main()
{
int i,j,n;
printf("请输入一个正整数：\n");
scanf("%d",&n);
printf("%d之前的素数有：\n",n);
for(i=2;i<=n;i++)
{
for(j=2;j<i;j++)
if(i%j==0) break;

if(j==i) printf(" %d\n",i);

}

}
n为100即可，望采纳！

Answer 3

//“筛选法”求素数。
#include "stdio.h"
void main()
{
int MAX=100;
int prime[30];
prime[0]=2; //已知的最小素数
int n=1; //素数个数,即数组的实际长度(元素个数)
int i=1; //下一个素数应存放的数组下标位置
int k=3; //从最小奇数开始测试,所有偶数不需测试
do
{
int j=0;
while ((j<n) && (k % prime[j]!=0)) //用已知素数prime[j]测试k
j++;
if (j==n) //k是素数
{
prime[i]=k; //将k添加到数组prime中
i++;
n++;
}
k+=2; //测试下一个奇数是否是素数
} while(k<MAX);

for (k=0;k<i;k++) //输出一维数组
{
printf("%d\t",prime[k]);
}
}
有注释自己看