数据结构与算法解析习题2.14：找出所有素数
这个主要用一个n+1（具体要不要+1根据后面给数组中元素赋值决定的，都可以）数组来记录素数的位置，比如7是素数，那么数组中index为7的元素就是1。
先把所有元素都置为1，然后在数组中非素数的index的元素，置为0，这样数组中为1的index，就是所有的素数了。
#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));
}