c++欧拉筛求素数个数代码

欧拉筛法是一种用于查找一定范围内所有质数的高效算法。它通过维护一个数组，记录每个合数因子的倍数已经被标记为合数，然后递归地筛选出所有的质数。以下是C++实现欧拉筛求素数个数的一个简化版本：

#include <iostream>
#include <vector>

void sieveOfEuler(int n, std::vector<bool>& isPrime) {
    isPrime.resize(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            // 将i的倍数标记为非素数
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    int count = 0;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) ++count;
    }
    std::cout << "Number of primes up to " << n << ": " << count << std::endl;
}

int main() {
    int limit;
    std::cout << "Enter a number: ";
    std::cin >> limit;
    std::vector<bool> isPrime(limit + 1);
    sieveOfEuler(limit, isPrime);
    return 0;
}

在这个代码中，`sieveOfEuler`函数接收一个整数n和一个布尔向量`isPrime`，其中`isPrime[i]`表示i是否为素数。首先初始化所有数字为素数，然后从2开始，逐个检查并标记其因子的倍数。最后，统计并输出小于或等于给定数值的素数个数。