用c++编写一个程序，求1-n的素数个数。给出两种解法，计算两种写法的求解时间

在C++中编写一个程序来求解1到n之间素数的个数，我们可以使用两种常见的算法：暴力法和埃拉托斯特尼筛法（Sieve of Eratosthenes）。下面是这两种方法的实现代码和性能评估方法。

1. 暴力法（Brute Force）：
暴力法是检查每个数是否为素数的方法。对于每个数，我们需要检查它是否能被更小的数整除。以下是代码实现：

#include <iostream>
#include <cmath>

bool isPrime(int num) {
    if (num <= 1) return false;
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

int countPrimes(int n) {
    int count = 0;
    for (int i = 1; i <= n; ++i) {
        if (isPrime(i)) {
            ++count;
        }
    }
    return count;
}

int main() {
    int n;
    std::cin >> n;
    std::cout << "Prime count from 1 to " << n << " is: " << countPrimes(n) << std::endl;
    return 0;
}

2. 埃拉托斯特尼筛法（Sieve of Eratosthenes）：
这是一种更加高效的算法，其基本思想是从最小的素数开始，找到所有的素数，并将这些素数的倍数标记为非素数。以下是代码实现：

#include <iostream>
#include <vector>

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

int main() {
    int n;
    std::cin >> n;
    std::cout << "Prime count from 1 to " << n << " is: " << countPrimes(n) << std::endl;
    return 0;
}

为了比较这两种算法的时间效率，我们可以记录它们的运行时间。在C++中，可以使用`<chrono>`库来测量时间。以下是测试代码的示例：

#include <chrono>
#include <iostream>

// ...（前面的函数实现）

int main() {
    int n;
    std::cin >> n;
    auto start = std::chrono::high_resolution_clock::now();
    std::cout << "Prime count from 1 to " << n << " is: " << countPrimes(n) << std::endl;
    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    std::cout << "Time elapsed: " << elapsed.count() << " seconds" << std::endl;
    return 0;
}