在线性时间里求素数表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
#include<cstring>
const int maxn = 1000000;
bool isPrime[maxn];
int table[maxn];
int cnt;
void getPrime()
{
    memset(isPrime,1,sizeof(isPrime));
    cnt = 0;
    isPrime[1] = 0;
    for(int i = 2; i < maxn; i++){
        if(isPrime[i]){
            table[++cnt] = i;
        }
        for(int j = 1; j <= cnt && i * table[j] < maxn; j ++){
            isPrime[i*table[j]] = 0;
        }
    }
}
int main()
{
    getPrime();
    for(int i = 1; i <= 20; i ++)
    {
        printf("%d\n",table[i]);
    }
}