用C＋＋编写（1）题目：求素数的个数。 （2）任务：对于给定的正整数n（超大数），求1~n的素数个数，给出两种解法。对于相同的n，给出这两种解法的结果和求解时间，并用相关数据进行测试。

在C++中，求素数的个数是一个经典的算法问题，特别是针对大数的时候，我们需要考虑效率。以下是两种常用的解法：

**解法一：埃拉托斯特尼筛法 (Sieve of Eratosthenes)**

这是一种简单而高效的算法，用于找出所有小于或等于指定数n的素数。步骤如下：

1. 创建一个布尔数组isPrime大小为n+1，初始化所有元素为true，表示所有数字都是素数。
2. 遍历从2到sqrt(n)，将每个素数的倍数标记为非素数。
3. 数组isPrime[i]为true的就是不超过n的素数。

#include <vector>
int countPrimes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    int primeCount = 0;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) primeCount++;
    }
    return primeCount;
}

**解法二：线性探测素数筛法**

这是一种改进版的筛法，通过更密集地存储素数并避免冗余计算，适用于非常大的n值。

// 这里简化了代码，实际实现需要一个优化的数据结构如Fenwick Tree等
int countPrimesLinear(int n) {
    bool* isPrime = new bool[n + 1];
    for (int i = 2; i <= n; i++) {
        isPrime[i] = true;
    }

    // 线性探测
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    int primeCount = 0;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) primeCount++;
    }
    delete[] isPrime;
    return primeCount;
}