原题链接：用筛法求之N内的素数
解题思路:
定义一个数组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分
44 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
大神我想问一下为什么我这个不行吗？求解答 #include<stdio.h> ss(int i) { int j; for(j=2;j<i;j++) { if(i%j==0) return 0; } } main() { int i,n,j,k; scanf("%d",&n); if(n!=1&&n!=0) { for(i=2;i<=n;i++) { if(ss(i)) printf("%d\n",i); } } }请问一下为什么我这个方法不行呢 #include <stdio.h> int main() { int n,i; scanf("%d",&n); for(i=0;i<n;i++) { if(i==0 || i==1) { continue; } if(i==2 || i==3 || i==5 || i==7) { printf("%d\n",i); } if(i%2!=0 && i%3!=0 && i%5!=0 && i%7!=0) { printf("%d\n",i); } } return 0; }大神看你的题解，我想到一个优化方法，就是那用筛选法，找到素数就直接输出，不用再用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; }