线性筛示例代码C++

线性筛，也叫埃拉托斯特尼筛法(Sieve of Eratosthenes)，是一种用于找出一定范围内所有质数的经典算法。以下是C++的一个简单实现：

#include <iostream>
#include <vector>

using namespace std;

// 筛选出不大于n的所有质数
void linearSieve(int n) {
    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) { // 将i的倍数标记为非质数
                isPrime[j] = false;
            }
        }
    }

    // 输出所有的质数
    for (int i = 2; i <= n; ++i)
        if (isPrime[i])
            cout << i << " ";
}

int main() {
    int n;
    cout << "请输入一个整数：";
    cin >> n;
    linearSieve(n);
    return 0;
}

在这个代码里，`linearSieve`函数首先创建了一个布尔向量`isPrime`，然后从2开始遍历，将每个质数的倍数标记为非质数。最后，遍历`isPrime`并打印出那些值为`true`的位置对应的数字，即为质数。