如何在C++中高效查找素?cái)?shù)

在C++中高效查找素?cái)?shù)可以使用篩選法，比如埃拉托斯特尼篩法（Sieve of Eratosthenes）。這種算法可以在O(nloglog(n))的時(shí)間復(fù)雜度內(nèi)找到小于n的所有素?cái)?shù)。

以下是一個(gè)使用埃拉托斯特尼篩法查找素?cái)?shù)的示例代碼：

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

在上面的代碼中，首先創(chuàng)建一個(gè)大小為n+1的布爾型數(shù)組isPrime，用來(lái)表示每個(gè)數(shù)字是否為素?cái)?shù)。然后從2開(kāi)始遍歷數(shù)組，將所有素?cái)?shù)的倍數(shù)標(biāo)記為非素?cái)?shù)。最后再遍歷數(shù)組，將所有標(biāo)記為素?cái)?shù)的數(shù)字放入primes數(shù)組中，最終返回primes數(shù)組即可。

這種方法可以高效地找到小于n的所有素?cái)?shù)，時(shí)間復(fù)雜度為O(nloglog(n))。