C++实现筛选法求2~200间素数

"用筛选取法（Sieve of Eratosthenes）求出2~200之间的所有素数，这是一种经典的算法，通过标记合数来找出素数。" 在编程领域，尤其是使用C++时，求解素数是一项常见的任务。筛选取法是一种高效且直观的方法，尤其适合于找出一个范围内所有的素数。该方法的基本思想是从小到大遍历数字，首先将2及其倍数标记为非素数，然后依次标记3的倍数、5的倍数等，直到遍历到平方根范围内的所有质数。在遍历过程中未被标记的数字即为素数。 以下是筛选取法的步骤： 1. 创建一个大小为n+1的布尔数组，所有元素初始值为true，表示所有数字都被认为是素数。 2. 从2开始，对于每个未被标记的数字i（即数组中的true），将其所有倍数标记为非素数（即数组中的false）。这些倍数包括i的2倍、3倍、4倍，直到n。 3. 遍历完成后，数组中值为true的索引对应的数字就是素数。 在这个例子中，给出了2~200范围内的筛选取法过程，可以看到，首先2、3是素数，接着将2的倍数（4、6、8...）标记为非素数，然后是3（5、9...），以此类推。最终，数组中未被0替换的数字代表它们是素数。 C++作为一种强大的编程语言，不仅支持基本的数据类型和控制结构，还拥有丰富的库函数和模板机制，使得实现这个算法变得简单。在C++中，我们可以使用标准模板库（STL）中的容器，如vector，来存储和处理数据。此外，C++11引入的范围基础的for循环（range-based for loop）使得遍历数组或容器更加简洁。 下面是一个简单的C++实现筛选取法求素数的代码示例： ```cpp #include <iostream> #include <vector> void sieveOfEratosthenes(int n) { std::vector<bool> primes(n + 1, true); primes[0] = primes[1] = false; for (int p = 2; p * p <= n; ++p) { if (primes[p]) { for (int i = p * p; i <= n; i += p) primes[i] = false; } } for (int p = 2; p <= n; ++p) { if (primes[p]) std::cout << p << " "; } } int main() { int limit = 200; sieveOfEratosthenes(limit); return 0; } ``` 这段代码首先初始化了一个大小为n+1的bool向量，然后按照筛选取法的规则进行遍历和标记。最后，输出向量中值为true的索引，即为2~200范围内的所有素数。 C++语言的灵活性和高效性使其成为实现各种算法的理想选择，而筛选取法作为解决特定问题的算法，展示了编程中逻辑思维和问题解决能力的重要性。通过学习和掌握C++以及类似筛选取法的算法，开发者可以更好地理解和编写高效、可维护的代码。