题意：给出n，求不大于n的素数有多少个。
算法：先用线性时间复杂度的筛法打素数表，对于每个输入统计不超过的素数个数。
#include <cstdio> int p[100010];
bool np[1000010];
int cntp; void SievePrime(int n) {
for (int i = 0; i <= n; ++i) np[i] = true;
np[0] = false, np[1] = false;
for (int i = 2; i <= n; ++i) {
if (np[i]) {
p[cntp++] = i;
for (int j = 2 * i; j <= n; j += i) {
np[j] = false;
}
}
}
} int main() {
SievePrime(1000000);
int n;
while (scanf("%d", &n) != EOF) {
int ans = 0;
for (int i = 2; i <= n; ++i) {
if (np[i]) ++ans;
}
printf("%d\n", ans);
}
return 0;
}