C++谭浩强课件：筛选法实现2~200范围内素数查找

在C++谭浩强编著的教材中，有一章节专门讲解如何使用筛选法求解2到200之间的所有素数。筛选法是一种高效查找素数的方法，其基本原理是先将给定范围内的所有数初始化为素数（1通常被排除在外），然后从最小的素数（2）开始，依次标记其倍数为非素数。具体步骤如下： 1. 初始化一个大小为n+1的布尔数组，其中索引表示数值，初始状态下所有元素都标记为素数（true）。 2. 从2开始，遍历数组，对于每个素数i，找到它的平方小于等于n的所有倍数，将这些倍数对应的数组元素置为false。例如，当i=2时，将所有偶数（除2本身外）标记为非素数；接着是i=3，将所有3的倍数（除3外）标记；以此类推，直到i*i > n。 3. 遍历完成后，数组中仍然标记为true的元素即为素数。筛选法的优势在于，随着i的增长，其倍数的标记会覆盖掉之前未被标记的素数，从而避免重复检查。 4. 在给定的示例中，可以看到数组的迭代过程：从2开始，2的倍数被标记为0，然后是3，5，7，…，依此类推。最终输出的数组中，非零的元素就是2到200之间的素数，如2、3、5、7、11、13、17、19等。 C++代码实现这个筛选法可能会这样设计： ```cpp #include <iostream> #include <vector> bool isPrime(int n) { if (n <= 1) return false; if (n == 2 || n == 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; } int main() { const int limit = 200; std::vector<bool> primes(limit + 1, true); primes[0] = primes[1] = false; for (int i = 2; i * i <= limit; i++) { if (primes[i]) { for (int j = i * i; j <= limit; j += i) { primes[j] = false; } } } for (int i = 2; i <= limit; i++) { if (primes[i]) { std::cout << i << " "; } } return 0; } ``` 这段代码首先创建了一个布尔向量`primes`，然后利用内层循环根据已知素数i更新其倍数为非素数。最后，输出非零元素，即为2到200之间的所有素数。通过这种方法，我们可以高效地找出给定范围内的素数。