如何用c++找出质数

在C++中，找出一个给定范围内的所有质数可以使用多种算法实现，这里提供一种常见的“埃拉托斯特尼筛法”（Sieve of Eratosthenes）。这个算法通过标记每一个合数的倍数，最终剩下的未被标记的就是质数。

以下是基本步骤：

#include <iostream>
#include <vector>

// 判断是否为质数
bool isPrime(int num) {
    if (num <= 1)
        return false;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0)
            return false;
    }
    return true;
}

// 使用埃拉托斯特尼筛法找质数
std::vector<int> findPrimes(int n) {
    std::vector<bool> isComposite(n + 1, false);
    for (int i = 2; i * i <= n; ++i) { // 只需到根号n即可
        if (!isComposite[i]) {
            for (int j = i * i; j <= n; j += i)
                isComposite[j] = true;
        }
    }

    std::vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (!isComposite[i])
            primes.push_back(i);

    return primes;
}

int main() {
    int limit;
    std::cout << "请输入一个整数范围上限: ";
    std::cin >> limit;
    std::vector<int> primeNumbers = findPrimes(limit);
    if (primeNumbers.empty()) {
        std::cout << "没有找到质数。";
    } else {
        std::cout << "在" << limit << "以内的质数有: ";
        for (const auto &prime : primeNumbers)
            std::cout << prime << " ";
    }
    return 0;
}