数据结构与算法解析习题2.14：找出所有素数

2019-03-06 约 309 字预计阅读 1 分钟

这个主要用一个n+1（具体要不要+1根据后面给数组中元素赋值决定的，都可以）数组来记录素数的位置，比如7是素数，那么数组中index为7的元素就是1。

先把所有元素都置为1，然后在数组中非素数的index的元素，置为0，这样数组中为1的index，就是所有的素数了。

 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
32
33



#include <stdio.h>

int countPrimes(int n) {

    int p[n + 1]; //p[i]=1 表示i是素数
    int tot = 0;

    for(int i = 2; i <= n; i++) p[i] = 1;

    // 遍历大于2的每一个数，然后把这些数的倍数（除了自己）都置0
    for(int i = 2; i <= n; i++)
        for(int j = i * 2; j <= n; j += i) p[j] = 0;

    for(int i = 2; i <= n; i++) if(p[i]) tot ++;

    for (int i = 2; i <= n; ++i) {

        if (p[i]) {
            printf("%d 是素数 \n", i);
        }
    }

    return tot;
}

int main() {

    printf("素数数量 = %d \n", countPrimes(72));

}

目录

数据结构与算法解析习题2.14：找出所有素数