用筛法求出n(2≤n≤1000)n(2≤n≤1000)以内的全部质数。
【输入】
输入n。
【输出】
多行,由小到大的质数。
【输入样例】
10
【输出样例】
2
3
5
7
#include<stdio.h>
#include<math.h>
int is_prime(int a){
if(a==1){return 0;}
else for(int i=2; i<=floor(sqrt(a)+0.5); i++){
if(a%i==0)return 0;
}
return 1;
}
int main(){
int n;
scanf("%d",&n);
int N[n+1];
for(int i=0; i<n+1; i++){
N[i]=1;
}
for(int i=2; i<n+1; i++){
if(is_prime(i)==1){
for(int o=2; o<n+1; o++){
if(o%i==0){
N[o]=-1;
}
}
}
}
for(int i=2; i<n+1; i++){
if(N[i]>0){
printf("%d\n",i);
}
}
return 0;
}