题目描述
求N内的素数。
输入格式
N
输出格式
0～N的素数
样例输入
100
样例输出
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
普通方法思路：
遍历2~N以内的数，再遍历 2~其中的一位数字i，看2~i中的数能否被i整除，以count计数，如果count=0，则表示没有能被i整除的数，那么这个数就为素数，代码如下：
#include<stdio.h> int main() { //素数就是除一和本身外没有其他的数能与它本身整除 int i,j,n,count;//count用来记录可以和i整除的数 scanf("%d",&n); for(i=2;i<=n;i++) { count=0;//注意每次都要重新赋零值，不然后面判定就错了 for(j=2;j<i;j++) { if(i%j==0) count++;//如果i是素数的话count应该是零的 } if(count==0) printf("%d\n",i);//如果是素数就就输出了记得要加换行符 } return 0; }
优化方法思路：在网上看到的一种方法，对于我来说是新的思路，在这里也分享给大家
•任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积
•所以若prime[i]==0,则prime[i*j]==1 即prime[i*j]不为素数
注：
prime[2]==0 表示2为素数 prime[8]==1 表示8不为素数
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; }
