C++谭浩强：筛选法实现2~200间素数查找

在C++编程领域，筛选法（Sieve of Eratosthenes）是一种古老且高效的算法，用于找出一个范围内的所有质数。在这个例子中，我们关注的是如何用C++实现从2到200之间的所有素数查找。筛选法的基本思想是，从最小的质数（2）开始，将它的倍数标记为非素数，然后移动到下一个未被标记的数，即下一个质数，重复此过程，直到遍历到所指定的上限。 以下是详细的步骤： 1. **C++概述**： C++是由Dennis Ritchie和Brian Kernighan在1972年基于B语言发展起来的，最初是为了编写UNIX操作系统。C++继承了C语言的灵活性和高效性，同时增加了面向对象编程的支持，使其在大型系统开发和性能优化方面表现出色。 2. **C语言特点**： - 结构化：C语言结构清晰，适合编写复杂程序，无论是大型系统还是小型控制程序，都能有效处理。 - 高级与低级特性结合：C语言提供丰富的运算符，包括算术和逻辑运算，以及位运算，允许直接操作内存，提高了代码效率。 - 可移植性：C语言编写的程序能够在多种计算机平台上运行，无需大量修改。 - 自由度与挑战：虽然语法灵活，但对新手而言可能需要更多实践和理解，调试过程可能相对复杂。 3. **筛选取法实现**： 在C++中，首先创建一个大小为200的数组，所有初始值设为1（表示可能是质数）。然后，从2开始，依次检查每个数，如果它是质数（即数组值为1），就将它的所有倍数（除了自身）标记为0，因为它们不是素数。这个过程持续到√200，因为一个大于√n的因数必定小于或等于√n，这有助于减少计算量。最后，数组中所有值为1的元素对应的索引就是素数。 下面是一个简单的C++代码实现： ```cpp #include <iostream> #include <vector> using namespace std; void sieveOfEratosthenes(int n) { vector<bool> primes(n+1, true); // 假设所有数都是质数 primes[0] = primes[1] = false; // 0和1不是质数 for (int i = 2; i * i <= n; i++) { if (primes[i]) { // 如果i是质数 for (int j = i * i; j <= n; j += i) { primes[j] = false; // 标记i的倍数为非素数 } } } // 输出素数 for (int i = 2; i <= n; i++) { if (primes[i]) cout << i << " "; } } int main() { sieveOfEratosthenes(200); return 0; } ``` 这段代码首先初始化一个布尔向量`primes`，然后通过两个嵌套循环，外部循环检查每个数，内部循环标记其倍数。最后，遍历`primes`数组并输出所有的素数。 通过这个例子，学习者可以理解C++中的数据结构（如向量）和如何利用筛选法高效求解素数问题。同时，这也展示了C++语言在处理算法问题时的灵活性和性能优势。