用C++ 实现素数算法

在C++中实现素数算法的一种常见方法是使用埃拉托斯特尼筛法（Sieve of Eratosthenes）。这是一种用于找出一定范围内所有质数的有效算法。以下是简单的实现步骤：

#include <iostream>
#include <vector>

std::vector<int> sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true); // 假设所有数字都是质数
    isPrime[0] = isPrime[1] = false; // 0和1不是质数

    for (int i = 2; i * i <= n; ++i) { // 只需检查到√n
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // 把结果存储在一个向量中
    std::vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (isPrime[i])
            primes.push_back(i);

    return primes;
}

int main() {
    int limit;
    std::cout << "Enter the upper limit for prime numbers: ";
    std::cin >> limit;

    std::vector<int> primes = sieveOfEratosthenes(limit);
    std::cout << "Primes up to " << limit << " are: ";
    for (const auto& prime : primes)
        std::cout << prime << " ";

    return 0;
}

在这个示例中，`sieveOfEratosthenes`函数会返回指定范围内的所有质数。用户可以输入一个整数，程序会输出该范围内所有的素数。