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

在C++程序设计中，谭浩强编著的教材中介绍了一种求解素数的方法，即筛法。这种算法用于寻找2到200之间的所有素数。筛法的基本原理是利用数组来存储从1到指定范围的数，初始时所有数都被标记为素数（非零）。然后从最小的素数2开始，将其倍数标记为合数（非素数），接着移动到下一个未被标记的数3，重复这个过程，直到遍历到当前范围内的最大素数。在这个例子中，数组的初始状态如下： ``` 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 3 0 5 0 7 0 9 0 11 0 13 0 15 0 17 0 19 0 2 3 0 5 0 7 0 0 0 11 0 13 0 0 0 17 0 19 0 ``` 步骤如下： 1. 首先，创建一个数组，长度为要查找范围的上限（这里是200），并将所有元素初始化为1（因为默认情况下所有数被视为素数）。 2. 从2开始，如果数组中的当前元素是素数（值为1），则输出该数。然后，将该数的所有倍数（2的倍数、4的倍数等）的数组元素设置为0，表示它们不是素数。 3. 继续检查下一个未被标记为0的数，重复上述过程，直到遍历完数组。 C++实现此算法的关键在于循环和条件判断。例如，以下是一个简化版的C++代码片段： ```cpp #include <iostream> #include <vector> bool isPrime(int num) { if (num <= 1) return false; for (int i = 2; i * i <= num; i++) { if (num % i == 0) return false; } return true; } void sieveOfEratosthenes(int n) { std::vector<bool> primes(n + 1, true); primes[0] = primes[1] = false; for (int i = 2; i * i <= n; i++) { if (primes[i]) { for (int j = i * i; j <= n; j += i) { primes[j] = false; } } } for (int i = 2; i <= n; i++) { if (primes[i]) { std::cout << i << " "; } } } int main() { sieveOfEratosthenes(200); return 0; } ``` 这段代码首先定义了一个`isPrime`函数来检查单个数是否为素数，然后在`sieveOfEratosthenes`函数中实现了筛法。最后，在`main`函数中调用该函数找出2到200之间的所有素数并打印出来。 C++语言在程序设计中的特点，如结构化、灵活性高、与低级语言结合以及良好的可移植性，使得它非常适合实现此类算法。然而，由于C++语法相对复杂，对于初学者来说可能需要一定时间去熟悉和掌握。尽管调试过程中可能存在挑战，但只要理解了C++的语法规则，编写和调试程序是可以逐步掌握的。