欧拉筛

### 关于欧拉筛算法的实现与优化 #### 欧拉筛的核心思想 欧拉筛是一种高效的线性筛法，能够在 \(O(n)\) 的时间复杂度内完成质数筛选。它的核心思想在于通过确保每个合数仅由其最小质因数筛除一次，从而避免了重复计算[^1]。 #### 欧拉筛的基本实现 以下是欧拉筛的经典实现代码： ```cpp #include <iostream> #include <vector> using namespace std; const int MAX_N = 1e7 + 5; bool is_prime[MAX_N]; // 是否为质数标志数组 vector<int> primes; // 存储所有质数 void sieve_of_euler(int n) { fill(is_prime, is_prime + n + 1, true); is_prime[0] = is_prime[1] = false; // 初始化 0 和 1 不是质数 for (int i = 2; i <= n; ++i) { if (is_prime[i]) { primes.push_back(i); // 如果当前数是质数，则加入列表 } for (int j = 0; j < primes.size() && primes[j] * i <= n; ++j) { is_prime[primes[j] * i] = false; // 将该合数标记为非质数 if (i % primes[j] == 0) break; // 当前合数已被其最小质因子处理过，跳出循环 } } } ``` 这段代码实现了基本的欧拉筛逻辑，其中 `if (i % primes[j] == 0)` 是关键条件之一，用于保证每个合数只会被其最小质因数筛掉一次[^3]。 #### 使用 Bitset 进一步优化空间和性能 为了进一步减少内存消耗并提升运行效率，可以利用 C++ 中的 `bitset` 容器替代传统的布尔型数组。由于 `bitset` 的每一位只占用 \(\frac{1}{8}\) 字节的空间，因此能够显著降低存储成本。下面是基于 `bitset` 的优化版本： ```cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 1e7 + 5; bitset<MAX_N> is_composite; // 标记是否为合数，默认初始化为false vector<int> primes; void optimized_sieve_of_euler(int n) { for (int i = 2; i <= n; ++i) { if (!is_composite[i]) { primes.push_back(i); // 若未被标记为合数，则为质数 } for (size_t j = 0; j < primes.size() && (long long)i * primes[j] <= n; ++j) { is_composite[i * primes[j]] = true; // 标记对应的合数 if (i % primes[j] == 0) break; // 确保每个合数只被最小质因数筛除一次 } } } int main() { int limit = 1e7; optimized_sieve_of_euler(limit); cout << "Number of primes up to " << limit << ": " << primes.size() << endl; return 0; } ``` 此版本不仅节省了大量内存资源，还因为位运算的优势提升了执行速度[^3]。 #### 总结 欧拉筛相比其他传统筛法具备更高的效率和更低的时间复杂度，在实际应用中非常广泛。通过引入 `bitset` 可以有效压缩数据结构所需的物理存储量，并且加速程序的整体表现。