解题思路:
定义一个数组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; }
直接去掉偶数的方法好啊!
#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-12-19 20:32:53 |
不好把自身输出