如何在C++中高效查找素数

在C++中高效查找素数可以使用筛选法，比如埃拉托斯特尼筛法（Sieve of Eratosthenes）。这种算法可以在O(nloglog(n))的时间复杂度内找到小于n的所有素数。

以下是一个使用埃拉托斯特尼筛法查找素数的示例代码：

#include <iostream>
#include <vector>

std::vector<int> findPrimes(int n) {
    std::vector<bool> isPrime(n+1, true);
    std::vector<int> primes;

    for (int p = 2; p*p <=n; p++) {
        if (isPrime[p]) {
            for (int i = p*p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            primes.push_back(p);
        }
    }

    return primes;
}

int main() {
    int n = 100;
    std::vector<int> primes = findPrimes(n);

    for (int prime : primes) {
        std::cout << prime << " ";
    }

    return 0;
}

在上面的代码中，首先创建一个大小为n+1的布尔型数组isPrime，用来表示每个数字是否为素数。然后从2开始遍历数组，将所有素数的倍数标记为非素数。最后再遍历数组，将所有标记为素数的数字放入primes数组中，最终返回primes数组即可。

这种方法可以高效地找到小于n的所有素数，时间复杂度为O(nloglog(n))。