欧拉筛-vector

欧拉筛（线性筛）是一种高效的筛选素数的算法，能够在 $ O(n) $ 的时间复杂度内找出小于等于 $ n $ 的所有素数。与埃氏筛法不同的是，欧拉筛通过确保每个合数只被其最小的质因子筛除一次，从而避免了重复标记的问题。 在 C++ 中，可以使用 `vector` 数据结构来实现欧拉筛，以动态存储筛选出的素数。这种方式不仅简化了代码，还提高了程序的可扩展性。以下是一个基于 `vector` 实现的欧拉筛算法示例： ```cpp #include <iostream> #include <vector> using namespace std; vector<int> primes; // 用于存储素数的 vector bool is_composite[1000001]; // 标记是否为合数的数组，默认初始化为 false void euler_sieve(int n) { for (int i = 2; i <= n; ++i) { if (!is_composite[i]) { primes.push_back(i); // 如果 i 是素数，则加入 vector } // 遍历当前已找到的素数列表 for (size_t j = 0; j < primes.size() && i * primes[j] <= n; ++j) { is_composite[i * primes[j]] = true; // 标记 i * primes[j] 为合数 if (i % primes[j] == 0) { break; // 如果 i 能被 primes[j] 整除，则停止循环 } } } } int main() { int n; cout << "请输入要筛选的最大值 n: "; cin >> n; euler_sieve(n); // 输出所有筛选出的素数 for (size_t i = 0; i < primes.size(); ++i) { cout << primes[i] << " "; } return 0; } ``` ### 算法说明： - **初始化**：定义一个布尔数组 `is_composite` 来标记每个数是否为合数，并定义一个 `vector<int>` 类型的 `primes` 来保存筛选出的素数。 - **主循环**：从 2 开始遍历到 $ n $，如果当前数 `i` 没有被标记为合数，则它是一个素数并被添加到 `primes` 中。 - **内层循环**：对于每一个已经找到的素数 `primes[j]`，计算 `i * primes[j]` 并将其标记为合数。当 `i` 能被 `primes[j]` 整除时，跳出循环以保证每个合数只被最小的质因子筛除一次。 ### 关键点： - **时间复杂度**：由于每个合数仅被其最小的质因子筛除一次，因此该算法的时间复杂度为 $ O(n) $ [^1]。 - **空间复杂度**：需要两个额外的空间，一个是 `is_composite` 数组，另一个是 `primes` 向量，空间复杂度约为 $ O(n) $。 ### 注意事项： - 使用 `vector` 时需要注意内存管理，尤其是在处理非常大的数据集时，应考虑性能和内存消耗。 - 对于非常大的数值范围（如 $ 10^7 $ 或更高），可能需要调整编译器设置或使用更高效的数据结构和内存分配策略。 ---