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

在C++程序设计领域，谭浩强的著作《C++程序设计》中，有一个重要的实践案例是用筛选法求解2到200之间的所有素数。筛选法，又称埃拉托斯特尼筛法，是一种古老且高效的算法，用于找出一定范围内所有素数。它的基本思想是通过初始化一个整数数组，然后从2开始，依次将所有该数的倍数标记为非素数。这样，经过一轮处理后，未被标记的数即为素数。 首先，数组中的每个数都被初始化为1，表示默认所有数都可能是素数。然后从2开始，对于每个素数，遍历数组，将它的倍数（除了自身）置为0，因为这些数不是素数。例如，当遇到2时，将所有2的倍数（如4、8、12等）标记为0；接着是3，将所有3的倍数标记；以此类推，直到处理完某个数的倍数后，再检查下一个素数。在筛选过程中，最后剩下的非零元素就是2到200之间的素数。 下面是C++代码实现这个筛选过程的一个简单版本： ```cpp #include <iostream> #include <vector> void sieveOfEratosthenes(int n) { std::vector<bool> isPrime(n+1, true); // 初始化所有数为可能的素数 isPrime[0] = isPrime[1] = false; // 0和1不是素数 for (int i = 2; i * i <= n; ++i) { // 只需检查到√n if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } // 输出所有素数 for (int i = 2; i <= n; ++i) { if (isPrime[i]) { std::cout << i << " "; } } } int main() { sieveOfEratosthenes(200); return 0; } ``` 在这个例子中，`sieveOfEratosthenes`函数接收一个整数n作为参数，然后利用布尔向量`isPrime`来跟踪每个数是否是素数。程序的执行效率很高，因为它只检查每个素数的平方根以下的倍数，避免了不必要的计算。 通过学习这种筛选取法，程序员能够理解如何在C++中实现高效的算法，同时也能体会到C++语言结构化编程的优势，如清晰的语法、灵活的数据类型以及良好的可移植性。然而，C++的语法特点也意味着初学者需要花费更多时间去理解和调试代码，但随着对语言规则的理解加深，编写和优化程序会变得越来越得心应手。