解题思路

先用筛法找出范围内的素数，再统计每个 n 以前的素数数量。

参考代码

// 先读入题目给出的数据。
// 再按照题目要求进行计算。
// 最后按规定格式输出答案。
#include <iostream>
using namespace std;
bool p[10000001];
int main() {
    int n, b[100], q = 0, mx = 0;
    // 先读入所有问题，找到需要处理的最大范围。
    while (cin >> n && n) { b[q++] = n; if (n > mx) mx = n; }
    // 先假设都是素数，再用筛法标记合数。
    for (int i = 2; i <= mx; i++) p[i] = true;
    for (int i = 2; i * i <= mx; i++) if (p[i]) for (int j = i * i; j <= mx; j += i) p[j] = false;
    // 每组数据从2数到n，统计其中的素数。
    for (int k = 0; k < q; k++) { int cnt = 0; for (int i = 2; i <= b[k]; i++) if (p[i]) cnt++; cout << cnt << endl; }
    return 0;
}

复杂度分析

排序需要 O(n^2) 时间；其余循环按照实际遍历次数计算。代码使用固定大小数组，额外空间复杂度为 O(1) 或 O(n)。