C++筛选法实现2~200范围内的素数查找

在C++程序设计领域，谭浩强的著作《C++程序设计》为我们提供了一种有效的算法来求解素数问题。本节内容主要关注如何利用筛选法找出2到200之间的所有素数。筛选法，又称埃拉托斯特尼筛法，是一种古老且高效的算法，用于寻找一定范围内所有素数。 筛选法的基本步骤如下： 1. **数组初始化**：首先创建一个长度为n+1的数组，将所有元素初始化为1（表示它们可能是素数）。例如，对于2到200，数组将是201个元素。 2. **标记非素数**：从2开始，依次检查每个数i（i>1）是否为素数。如果i是素数，则将其倍数（即i的2倍、3倍等，直到这个倍数超过数组范围）标记为非素数，即将这些位置的数组值置为0。例如，2的倍数、3的倍数、5的倍数等都被标记为非素数。 - 对于2，直接标记2的倍数（如4,8,12...）； - 对于3，标记3的倍数（如6,9,12...）； - 对于5，标记5的倍数（如10,15,20...）； - 这个过程一直持续到√n，因为如果一个数不是素数，那么它的因子必然有一个小于或等于它的平方根。 3. **输出素数**：最后，数组中未被标记为0的元素就是素数。遍历整个数组，打印出所有值为1的元素及其对应的索引，这些索引对应的原始数就是素数。 在给出的示例中，数组的变化展示了筛选过程。开始时，所有数都被标记为可能的素数，然后逐个排除非素数，最终仅剩下2, 3, 5, 7, 11, 13, 17, 19这些素数。 C++中的实现会涉及循环、条件判断和数组操作，比如`for`循环和`if`语句，以及可能的`vector`或`bitset`等数据结构来简化处理。这种筛选法不仅展示了C++语言的灵活性，还演示了编程中优化算法以提高效率的重要原则。 学习C++时，理解并掌握这种素数筛选方法对于基础算法和数据结构的学习非常有帮助，同时也能锻炼逻辑思维和编程实践能力。C++语言的特点，如结构化、灵活、可移植性和相对宽松的语法，使得这种筛选法的实现更加方便。虽然调试初期可能会遇到挑战，但通过实践和理解语法规则，程序员能够逐步掌握并熟练运用。