解题思路:


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

ex:

    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);
}


 

0.0分

79 人评分

  评论区

大神看你的题解,我想到一个优化方法,就是那用筛选法,找到素数就直接输出,不用再用for循环找相应的值。
#include"stdio.h"
int main()
{
	int a[1000]={0};
	int i,j,n;
	scanf("%d",&n);
	for(i=2;i<n;i++)
		if(a[i]==0)
			{
				printf("%d\n",i);//满足条件就为素数,直接输出即可
				for(j=2;i*j<n;j++)
				a[i*j]=1;
			}
	return 0;
}
2019-05-20 10:21:33
直接去掉偶数的方法好啊!
2019-03-30 15:48:14
#include<stdio.h>
int main(){
	int i=3,n;
	scanf("%d",&n);
	if(n>2){
		printf("2\n");
    	while(i<=n){
		    int k;
		    for(k=2;k<=i;k++){
			    if(i%k==0 && i!=k){
			    	break;
		    	}
			    else if(i%k==0 &&i==k){
			    	printf("%d\n",k);
			    }
		    }
		    i=i+2;
        }
    }
	return 0;	
}
将 i 的跨步改为2,能省一半的内存
2019-03-03 17:14:33
m=floor(sqrt(n)+0.5);
2019-01-20 12:46:41
最后的for循环应该小于等于n,不然当n为素数时,会把它漏掉
2018-12-02 20:52:22
这会漏掉2这个素数。
2018-11-21 05:47:11
通过改变条件可以优化程序运行速度
2018-11-21 05:36:45