c++求小于等于n的所有素数的算法及实现

在C++中求小于等于n的所有素数，可以使用经典的埃拉托斯特尼筛法（Sieve of Eratosthenes），该算法的基本思想是从最小的素数开始，将所有该素数的倍数标记为非素数，然后找下一个未被标记的数，重复这个过程，直到达到需要的范围。

以下是使用埃拉托斯特尼筛法求小于等于n的所有素数的一个简单实现：

#include <iostream>
#include <vector>
#include <cmath>

std::vector<int> sieveOfEratosthenes(int n) {
    std::vector<bool> prime(n+1, true); // 初始化一个布尔数组，默认所有数都是素数
    std::vector<int> primes; // 存储所有素数

    prime[0] = prime[1] = false; // 0和1不是素数，所以标记为非素数

    for (int p = 2; p*p <= n; ++p) {
        if (prime[p]) {
            // 将当前素数p的所有倍数标记为非素数
            for (int i = p*p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }

    // 收集所有素数到primes向量中
    for (int p = 2; p <= n; ++p) {
        if (prime[p]) {
            primes.push_back(p);
        }
    }

    return primes;
}

int main() {
    int n;
    std::cout << "请输入一个整数n，以求得小于等于n的所有素数: ";
    std::cin >> n;

    std::vector<int> primes = sieveOfEratosthenes(n);

    std::cout << "小于等于" << n << "的所有素数有：" << std::endl;
    for (int prime : primes) {
        std::cout << prime << " ";
    }
    std::cout << std::endl;

    return 0;
}

这段代码首先创建了一个布尔类型的向量`prime`，其中的每个元素对应一个数，若该数是素数则为`true`，否则为`false`。通过循环检查每个数的倍数，将非素数标记为`false`。最后，将所有标记为`true`的索引（即素数）输出到一个整数向量`primes`中，并返回该向量。