nyoj 187 快速查找素数

快速查找素数

时间限制：1000ms | 内存限制：65535KB难度：3

描述

现在给你一个正整数N，要你快速的找出在2.....N这些数里面所有的素数。

输入

给出一个正整数数N(N<=2000000)

但N为0时结束程序。

测试数据不超过100组

输出

将2~N范围内所有的素数输出。两个数之间用空格隔开

样例输入

5
10
11
0

样例输出

2 3 5
2 3 5 7
2 3 5 7 11

来源

经典题

上传者

路过这

直接素数打表

View Code

1  
 2 /*********************************
 3 /   Problem:
 4 /   Algorithm:
 5 /   Language:   C++
 6 /   Compiler:   MinGW
 7 /   Date:       12/08/10
 8 /
 9 /   Copyright (C) wujianwei
10 /   All rights reserved.
11 ********************************/
12 
13 #include <iostream>
14 #include <cstdio>
15 #include <cstring>
16 #include <cmath>
17 #include <vector>
18 #include <cstring>
19 #include <queue>
20 #include <stack>
21 #include <algorithm>
22 #include <set>
23 
24 using namespace std;
25 
26 #define INF 0x7fffffff
27 #define EPS 1e-12
28 #define MOD 1000000007
29 #define PI 3.141592653579798
30 #define N 2000010
31 const int MAX=1<<28;
32 //typedef long long LL;
33 //typedef __int64 INT
34 int a[5000];
35 bool b[N];
36 
37 void prime()
38 {
39     int ans=0,i,j;
40     for(i=2;i<N;i++)
41     {
42         if(!b[i]) a[ans++]=i;
43         for(j=i+i;j<N;j+=i)
44             b[j]=1;
45     }
46 }
47 
48 int main()
49 {
50     int n;
51     prime();
52     while(scanf("%d",&n)&&n)
53     {
54         int i=0;
55         int k=0;
56         while(n>=a[i])
57         {
58             if(!k)
59             {
60                 printf("%d",a[i++]);
61                 k++;
62             }
63             else printf(" %d",a[i++]);
64         }
65         printf("n");
66     }
67     return 0;
68 }
69

原文链接: https://www.cnblogs.com/wujianwei/archive/2012/08/13/2637042.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍