AOJ 483.求素数

168


题目


点击显/隐题目

用筛选法求(1,n]之内的全部素数





行1:一个整数n,n∈[2,100000]





每行输出一个素数,由小到大排列





20





2
3
5
7
11
13
17
19





题解


算法模板题

筛法求素数

直接套用模板即可



代码


点击显/隐代码
`cpp 求素数 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include
//*/
#include
#include
#include
#include
using namespace std;

const int maxn = 100005;
bool is_prime[maxn+1];

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.syncwithstdio(0);

int n;
cin >> n;

int m=sqrt(n+0.5);
memset(isprime,true,sizeof(isprime));
for(int i=2;i<=m;i++){
if(is_prime[i]){
for(int j=i*i;j<=n;j+=i){
is_prime[j]=false;
}
}
}
for(int i=2;i<=n;i++){
if(is_prime[i]==true){
cout<}
}



#ifdef debug
printf("Time:%.3fs.n", double(clock() - START) / CLOCKSPERSEC);
#endif
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论