在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++的语法特点也意味着初学者需要花费更多时间去理解和调试代码,但随着对语言规则的理解加深,编写和优化程序会变得越来越得心应手。