素数的线性筛选法

素数的线性筛法也被称为埃拉托斯特尼筛法（Eratosthenes Sieve）。

素数的线性筛法是一种高效地筛选出一定范围内所有素数的算法。其基本思想是从小到大遍历每个数，对于每个数，将其所有的倍数标记为合数，剩下的即为素数。

具体步骤如下：
初始化一个大小为n+1的bool数组is_prime，所有元素初始化为true，表示都是素数。

从2开始遍历到sqrt(n)：

如果当前数字i是素数（即is_prime[i]为true），则将其所有的倍数标记为合数。即，从i*i开始，每隔i标记一个合数，直到大于n为止。

遍历完所有数字后，剩下的为素数。

这种方法的关键在于每个合数都被它的最小质因数筛掉，而且每个合数只会被筛选一次，因此效率很高。时间复杂度为O(nloglogn)，空间复杂度为O(n)。

【参考程序】

#include <iostream>
#include <vector>
using namespace std;

vector<int> linearSieve(int n) {
    vector<int> primes; // 存放素数
    vector<int> is_prime(n + 1, true); // 标记是否为素数，默认全为true

    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i); // 当前数是素数，加入素数数组
        }
        // 将当前素数的所有倍数标记为合数
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) { // 跳出内层循环
                break;
            }
        }
    }

    return primes;
}

int main() {
    int n;
    cout << "Enter the range (n): ";
    cin >> n;

    vector<int> primes = linearSieve(n);

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

    return 0;
}

经典算法

素数的线性筛选法