一个快速的筛选从0到一个数字之前所有素数的方法,思路比较简单:先把所有数字都标记为素数,然后从2开始一直到n,当这个数字i的标记为素数,就把 i i, i (i+1), i * (i+2), … , 全部标记为非素数即可。

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
29
30
31
#include <iostream>
using namespace std;

// max number
#define MAXN 1024

int main () {
bool is_prime[MAXN+1];
for (int i = 0; i <= MAXN; i++){
is_prime[i] = true;
}
is_prime[0] = false;
is_prime[1] = false;
for (int i = 2; i <= MAXN; i++){
if (is_prime[i]){
for (int j = i * i; j <= MAXN; j += i){
is_prime[j] = false;
}
}
}
// done for judge all number wether it is a prime.
// ----------------------------------------------
// output all prime number between 0-MAXN
for (int i = 0; i <= MAXN; i++){
if(is_prime[i]){
printf("%d ", i);
}
}
printf("\n");
return 0;
}