输入n，求1到n的素数个数，给出两种c++编程解法和求解时间

当你需要计算从1到n的素数个数时，可以采用埃拉托斯特尼筛法（Sieve of Eratosthenes）和质因数分解法这两种常见的算法来实现。

**第一种方法：埃拉托斯特尼筛法**

#include <iostream>
#include <vector>

int countPrimes(int n) {
    std::vector<bool> isPrime(n+1, true); // 初始化所有数字为素数
    isPrime[0] = isPrime[1] = false; // 0和1不是素数

    for (int i = 2; i * i <= n; ++i) { // 只需考虑到√n
        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;
}

此法的时间复杂度是O(n log log n)，因为每个非素数只需要筛选一次。

**第二种方法：质因数分解法**

#include <iostream>
using namespace std;

int countPrimes(int n) {
    int count = 0;
    for (int i = 2; i <= n; ++i) {
        bool isPrime = true;
        for (int j = 2; j*j <= i; ++j) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
            count++;
    }
    return count;
}

这种方法的时间复杂度是O(n²)，因为它对每一个数都进行了质因数检查。

**求解时间：**
- 埃拉托斯特尼筛法更优，适合较大的n值，因为其线性前缀操作次数远少于逐个判断。
- 质因数分解法则适用于较小范围内的n值，效率较低。