c++求1-n中素数的个数

在C++中，计算1到n之间的素数个数可以采用埃拉托斯特尼筛法（Sieve of Eratosthenes）或者更为复杂一些的算法，如米勒-拉宾素数检验结合筛选。这里我们介绍一种常见的基于筛法的方法。

埃拉托斯特尼筛法的基本思想是从小到大逐个标记出所有合数（即非素数），然后计数剩余未被标记的数字，它们就是素数。以下是简单的步骤：

1. 创建一个大小为n+1的布尔数组isPrime，初始值全部设为true，表示从2到n的所有数字都是待检查的素数。
2. 遍历数组，从第一个质数2开始，将它的倍数都标记为合数（isPrime[i] = false）。接着找到下一个未被标记的数字（当前的i + i），重复这个过程直到i的平方大于n。
3. 数组中剩下的所有true元素对应的索引即为素数，计数即可。

#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) {
        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;
}

int main() {
    int n;
    std::cout << "Enter a number: ";
    std::cin >> n;
    int result = countPrimes(n);
    std::cout << "Number of primes between 1 and " << n << " is: " << result << std::endl;
    return 0;
}