详细讲解线性筛法
线性筛法是一种用于求解素数的算法，其主要优点是时间复杂度较低，能够有效地生成一定范围内的所有素数。下面是线性筛法的详细讲解：
算法步骤
初始化：
设定一个布尔数组
is_prime，其中is_prime[i]表示数字i是否为素数。初始时，将数组中所有的值设为true，然后设置is_prime[0]和is_prime[1]为false，因为 0 和 1 不是素数。筛选素数：
从 2 开始遍历每个数字
i。对于每个i，如果is_prime[i]为true，说明i是一个素数。对于每个找到的素数
i，需要将i的所有倍数标记为非素数，即is_prime[i * j]设置为false，其中j从i开始到N / i。这个步骤使用了“线性”筛法中的重要特性：每个合数的标记是通过其最小素因子来完成的，这避免了重复的标记操作。优化：
为了避免重复标记，可以使用
min_prime数组来记录每个数字的最小素因子。这样，在筛选倍数时只需要从当前素数开始标记，避免了多次标记的情况。输出结果：
遍历布尔数组
is_prime，将标记为true的索引即为素数，输出这些素数。
时间复杂度
线性筛法的时间复杂度是 O(N log log N)，其中 N 是待筛选的最大值。这是因为每个素数 i 仅会影响其倍数一次，因此总体操作次数相对较少。
示例
假设要找到 1 到 30 之间的所有素数：
初始化布尔数组
is_prime为 [false, false, true, true, ..., true]（长度为 31）。从 2 开始，标记所有倍数：
对于
i=2，标记 4, 6, 8, ..., 30。对于
i=3，标记 9, 12, 15, ..., 30。对于
i=5，标记 25, 30（注意 30 已经被 2 标记过）。对于
i=7，标记 28。最终，
is_prime数组中标记为true的位置表示素数，即 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]。
总结
线性筛法的核心思想是通过逐个素数筛选其倍数来标记非素数，避免了重复标记操作。其时间复杂度相对较低，适合处理较大的范围内的素数查找问题。
以下是使用C++实现线性筛法的代码示例：
#include <iostream>
#include <vector>
void linearSieve(int n, std::vector<int>& primes, std::vector<bool>& is_prime) {
// 初始化
is_prime.assign(n + 1, true);
is_prime[0] = is_prime[1] = false;
// 线性筛法
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
primes.push_back(i); // i 是素数
}
for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
is_prime[i * primes[j]] = false; // 标记 i * primes[j] 不是素数
if (i % primes[j] == 0) {
break; // 保证每个合数只被其最小的素因子标记一次
}
}
}
}
int main() {
int n = 30; // 设定筛选范围
std::vector<int> primes; // 用于存储素数
std::vector<bool> is_prime; // 用于标记是否为素数
linearSieve(n, primes, is_prime);
// 输出结果
std::cout << "Primes up to " << n << " are: ";
for (int prime : primes) {
std::cout << prime << " ";
}
std::cout << std::endl;
return 0;
}