c++算法——欧拉筛

### 实现埃拉托色尼筛法的C++代码 为了提供一个具有良好编码风格和实践的埃拉托色尼筛法(C++版本)，下面展示了一个简洁而高效的实现方式。此算法用于找出小于给定整数`n`的所有素数。 ```cpp #include <iostream> #include <vector> using namespace std; // Function to implement the Sieve of Eratosthenes algorithm. void eratosthenes_sieve(int n) { vector<bool> is_prime(n + 1, true); int count = 0; // Mark non-prime numbers as false. Note that we start from p*p because any smaller multiple of p would have already been marked by a smaller prime factor. for (int p = 2; p * p <= n; ++p) { if (is_prime[p]) { // Update all multiples of p starting from square of it. for (int i = p * p; i <= n; i += p) is_prime[i] = false; } } cout << "Prime numbers up to " << n << ": "; for (int p = 2; p <= n; ++p) { if (is_prime[p]) { cout << p << ' '; ++count; } } cout << "\nTotal primes found: " << count << endl; } ``` 上述代码通过布尔向量来标记哪些数值是质数，从而有效地实现了埃拉托色尼筛法[^1]。对于每一个找到的新质数，其所有的倍数都会被设置为非质数状态。这种方法不仅直观而且效率高，特别适合处理较大的输入范围。 此外，这段代码还展示了如何利用标准模板库(STL)中的容器类——如`std::vector`，以及基本的数据结构操作，体现了现代C++编程的良好习惯。