C++程序设计：筛选取法实现2~200素数

"用筛选取法求出2~200之间的所有素数。-c++程序设计课件" 本文将探讨如何使用筛选取法（也称为埃拉托斯特尼筛法）在C++中找出2到200之间的所有素数。筛选取法是一种有效的寻找素数的方法，通过消除已知素数的倍数，逐步确定剩余的数是否为素数。 筛选取法的基本步骤如下： 1. 创建一个长度为n+1（这里n为200）的布尔数组，初始化所有元素为true，表示所有数字默认为素数。 2. 从2开始遍历数组，如果当前数字为true，说明它是素数，那么将其所有倍数标记为false，因为它们不可能是素数。例如，当i=2时，将2的所有倍数（如4,6,8...）标记为false。 3. 继续遍历，找到下一个未被标记的true值，这将是下一个素数。重复步骤2的过程，直到遍历完整个数组。 4. 遍历完成后，数组中为true的索引对应的数值就是素数。 在C++中实现这个算法，我们可以创建一个bool类型的vector或数组，然后按照上述步骤进行操作。以下是一个简单的C++代码示例： ```cpp #include <iostream> #include <vector> void sieveOfEratosthenes(int n) { std::vector<bool> isPrime(n + 1, true); for (int p = 2; p * p <= n; p++) { if (isPrime[p]) { for (int i = p * p; i <= n; i += p) isPrime[i] = false; } } // 打印素数 for (int p = 2; p <= n; p++) if (isPrime[p]) std::cout << p << " "; } int main() { int limit = 200; sieveOfEratosthenes(limit); return 0; } ``` 这段代码首先创建了一个大小为`limit+1`的`isPrime`向量，然后使用两个嵌套循环来筛选素数。外层循环从2开始，每次增加1，内层循环则从当前素数的平方开始，每次增加该素数的值，直到超过`limit`。这样做的目的是减少不必要的计算，因为一个合数的最小质因数不会超过它的平方根。 C++作为一种强大的编程语言，它结合了高级语言的抽象能力和低级语言的效率。C++中的面向对象特性使得代码组织更有序，而丰富的库支持则提供了多种数据结构和算法供开发者使用。对于学习C++的初学者，理解并熟练掌握筛选取法是程序设计基础的一个重要部分，它有助于提升对算法和数据结构的理解。 同时，C++语言有以下几个显著特点： 1. 结构化编程：C++支持结构化编程，它的控制结构包括if、switch、for、while等，使得程序逻辑清晰，易于理解和维护。 2. 高级和汇编语言的融合：C++具有丰富的运算符和数据类型，同时支持位操作，使得它在处理底层硬件方面也很强大。 3. 可移植性：C++程序可以在不同平台之间轻松迁移，只需要极少或无需修改。 4. 语法规则灵活：这使得C++能够适应各种编程风格，但同时也增加了学习曲线，需要程序员有较高的编程素养。 通过学习和实践C++，开发者可以构建高效、可扩展的软件系统，无论是操作系统、游戏引擎还是科学计算应用，C++都能提供必要的工具和支持。