求1亿以内所有素数的个数 c++

在C++中计算1亿以内的素数个数，可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）这个经典算法。以下是基本步骤：

1. 创建一个布尔数组isPrime[100000001]，并将所有元素初始化为true，表示从2到1亿都是潜在的素数。
2. 遍历数组，从第一个素数2开始，将它的倍数标记为非素数（isPrime[i]设为false）。因为所有的偶数除了2之外都不是素数。
3. 继续找到下一个未被标记为非素数的数字（称为当前的素数），更新它，并继续标记其倍数。
4. 当遍历到当前素数大于平方根100000000后，剩下的未被标记的就是素数了，因为超过该值的因子已经被之前的步骤处理过了。

下面是一个简单的C++代码示例：

#include <iostream>
#include <cmath>

int countPrimes(int n) {
    bool isPrime[n + 1];
    memset(isPrime, true, sizeof(isPrime));
    
    for (int p = 2; p * p <= n; ++p) {
        // 如果isPrime[p]仍然是true，则它是素数
        if (isPrime[p]) {
            // 标记p的所有倍数为非素数
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    int primeCount = 0;
    for (int p = 2; p <= n; ++p)
        primeCount += isPrime[p]; // 累加素数计数

    return primeCount;
}

int main() {
    int limit = 100000000;
    int primesInRange = countPrimes(limit);
    std::cout << "1亿以内的素数个数: " << primesInRange << "\n";
    return 0;
}