1
#include <stdio.h>
2
#include <time.h>
3

4
#define MAXN 1000
5

6
int main() {
7
    int prime[MAXN];
8
    int isComposite[MAXN+1] = {0};
9
    int count = 0;
10

11
    clock_t start_time, end_time;
12
    double time_used;
13

14
    start_time = clock();
15

16
    for (int i = 2; i <= MAXN; i++) {
17
        if (!isComposite[i]) {
18
            prime[count++] = i;
19
            printf("%d\n", i);
20
        }
21
        for (int j = 0; j < count && i * prime[j] <= MAXN; j++) {
22
            isComposite[i * prime[j]] = 1;
23
            if (i % prime[j] == 0)
24
                break; //保证一个合数只被标记一次
25
        }
26
    }
27

28
    printf("2-1000有 %d 个质数", count);
29

30
    end_time = clock();
31
    time_used = (double)(end_time - start_time) / CLOCKS_PER_SEC;
32
    printf("\n用时 %f 秒\n", time_used);
33

34
    return 0;
35
}