在 C++ 里，为了找出一定范围内的所有素数，埃氏筛法（埃拉托斯特尼筛法）和线性筛法（欧拉筛法）是两种常用的算法。下面为你详细总结这两种算法。

1. 素数定义
素数，也叫质数，是指一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数。例如 2、3、5、7 等都是素数。

2. 埃氏筛法（埃拉托斯特尼筛法）
原理
该算法的核心思想是从 2 开始，将每个素数的倍数标记为合数，逐步筛选出所有素数。具体来说，先假设所有数都是素数，然后从最小的素数 2 开始，把 2 的倍数（除 2 本身）都标记为合数；接着找到下一个未被标记的数，它就是素数，再把它的倍数标记为合数，依此类推，直到遍历完所有小于等于给定范围的数。

代码实现

#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) {
        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 n = 30;
    std::vector<int> primes = sieveOfEratosthenes(n);

    std::cout << "Prime numbers up to " << n << " are: ";
    for (int prime : primes) {
        std::cout << prime << " ";
    }
    std::cout << std::endl;

    return 0;
}

复杂度分析

• 时间复杂度：约为 O(n log log n)。这是因为对于每个素数 p，需要标记 n/p 个数为合数，对所有素数求和得到时间复杂度。
• 空间复杂度：O(n)，主要用于存储标记数组。

优缺点

• 优点：实现简单，易于理解，对于较小范围的素数筛选效率较高。
• 缺点：会有重复标记的情况，例如 6 会被 2 和 3 都标记一次，导致效率有一定损失。

3. 线性筛法（欧拉筛法）
原理
线性筛法在埃氏筛法的基础上进行了优化，保证每个合数只会被它的最小质因数筛去，从而避免了重复标记，实现了线性时间复杂度。具体做法是在遍历过程中，对于每个数 (i)，都与已找到的素数表中的素数相乘，并标记乘积为合数，当 (i) 能被当前素数整除时就停止，这样可以确保每个合数只被其最小质因数筛一次。

代码实现

#include <iostream>
#include <vector>

// 线性筛法求素数
std::vector<int> eulerSieve(int n) {
    std::vector<bool> isPrime(n + 1, true);
    std::vector<int> primes;
    isPrime[0] = isPrime[1] = false;  // 0 和 1 不是素数

    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            isPrime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }

    return primes;
}

int main() {
    int n = 30;
    std::vector<int> primes = eulerSieve(n);

    std::cout << "Prime numbers up to " << n << " are: ";
    for (int prime : primes) {
        std::cout << prime << " ";
    }
    std::cout << std::endl;

    return 0;
}

复杂度分析

• 时间复杂度：O(n)，因为每个数只会被筛一次，避免了埃氏筛法的重复标记问题。
• 空间复杂度：O(n)，主要用于存储标记数组和素数表。

优缺点

• 优点：时间复杂度为线性，效率高，尤其适用于大范围的素数筛选。
• 缺点：代码实现相对复杂一些，理解起来有一定难度。

4. 总结

• 埃氏筛法实现简单，对于较小范围的素数筛选足够高效，当对代码简洁性要求较高且范围不大时可优先选择。
• 线性筛法时间复杂度更优，适合处理大范围的素数筛选问题，但实现相对复杂，在对性能要求极高的场景下使用更为合适。