用埃氏筛法求1-n的素数

埃氏筛法（Sieve of Eratosthenes）是一种用于求解素数的经典算法。它的基本思想是从2开始，将每个素数的倍数标记为合数，直到遍历完所有小于等于n的数。最后剩下的未被标记的数即为素数。

以下是使用埃氏筛法求解1到n的素数的C++代码示例：

#include <iostream>
#include <vector>

std::vector<int> sieveOfEratosthenes(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; // 将p的倍数标记为合数
            }
        }
    }

    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            primes.push_back(p); // 将未被标记的数加入素数容器
        }
    }

    return primes;
}

int main() {
    int n;
    std::cout << "请输入一个正整数n：";
    std::cin >> n;

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

    std::cout << "1到" << n << "的素数有：";
    for (int prime : primes) {
        std::cout << prime << " ";
    }
    std::cout << std::endl;

    return 0;
}

运行示例：

请输入一个正整数n：20
1到20的素数有：2 3 5 7 11 13 17 19

在上述代码中，我们使用了一个布尔类型的标记数组`isPrime`来记录每个数是否为素数。初始时，将所有数都标记为素数。然后从2开始遍历，如果当前数是素数，则将其倍数标记为合数。最后遍历标记数组，将未被标记的数加入素数容器。