C++面向对象：筛选取法实现2~200间素数查找

在C++面向对象程序设计中，"用筛选取法求出2~200之间的所有素数"是一个常见的编程练习，它涉及到基础算法和数据结构的运用。筛选法，也称为埃拉托斯特尼筛法（Sieve of Eratosthenes），是一种古老且高效的求解素数的方法。这种方法的基本思想是从最小的质数2开始，将其倍数标记为合数（非素数），然后移动到下一个未被标记的数（即下一个质数），重复此过程，直到处理完所有小于或等于目标范围的数。 以下是如何使用C++实现这个算法的步骤： 1. 定义一个大小为目标范围（例如200）加一的布尔型数组，初始时所有元素设为`true`，表示每个数都被假设为可能的素数。 2. 从2开始，遍历数组。对于每一个素数2，将它的所有倍数（2的倍数、4的倍数、6的倍数等）的数组元素设为`false`，因为它们不是素数。 3. 继续寻找下一个未被标记为`false`的元素，即下一个质数。找到后，再次遍历该数的倍数并标记为非素数。 4. 当遍历完整个数组，剩下的所有`true`值对应的数字就是2到指定范围内的素数。 以下是一个简单的C++代码示例： ```cpp #include <iostream> #include <vector> bool isPrime(int n, std::vector<bool>& primes) { 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; } void sieveOfEratosthenes(int n, std::vector<bool>& primes) { primes.resize(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; } } } } int main() { int limit = 200; std::vector<bool> primeArray(limit + 1, true); sieveOfEratosthenes(limit, primeArray); for (int i = 2; i <= limit; ++i) { if (primeArray[i]) std::cout << i << " "; } return 0; } ``` 这段代码首先定义了一个`isPrime`函数，用于判断单个数是否为素数，然后在`sieveOfEratosthenes`函数中应用筛选法。在`main`函数中，我们创建一个布尔数组并调用筛选函数，最后打印出2到200之间的所有素数。 C++作为一种强大的编程语言，它在面向对象设计中提供了类和对象的概念，这使得代码更加模块化和易于维护。在实际编程中，我们可以将上述方法封装到一个名为`PrimeFinder`的类中，包含成员函数如`findPrimes`，这样更符合面向对象的设计原则。同时，C++的模板和STL库也可以帮助我们更好地处理各种规模的问题，提高代码的复用性和效率。学习这种筛选法并应用于C++编程，有助于理解基础算法和优化代码性能。