【编程经验】优秀题解

解题思路:

定义一个数组prime[],赋初值为0，数组下表对应这个数字，通过数组值来判断是否为素数

ex:

1

prime[2]==0 表示2为素数 prime[8]==1 表示8不为素数

根据算术基本定理：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积

所以若prime[i]==0,则prime[i*j]==1 即prime[i*j]不为素数

只要i：2->n 即可构建n以内的质数表

注意事项: prime[0]=prime[1]=1; //0 1特殊处理

参考代码:

#include<stdio.h>

int main(){

int prime[10000]={0};

int i,j;

int n;

scanf("%d",&n);

prime[0]=prime[1]=1;

for(i=2;i<n;i++)

if(prime[i]==0)

for(j=2;i*j<=n;j++)

prime[i*j]=1;

for(i=0;i<n;i++)

if(prime[i]==0)

printf("%d\n",i);

return 0;

}

下面是另一种求素数方法

#include<stdio.h>

#include<math.h>

void judge(int n);

//----------------------------*

int main(void){

int n,i;

scanf("%d",&n);

for(i=2;i<=n;i++)

if(i%2!=0) //去偶数

judge(i);

return 0;

}

//----------------------------*

void judge(int n){

int i,flag=0;

double sq;

sq=sqrt(n); //减少开根运算

for( i=2;i<=sq;i++) //因数都是成对存在的 而且因数对一定是一大一小（除平方根）

if(n%i==0){

flag=1;

break;

}

if(flag==0)

printf("%d\n",n);

}