C++程序设计：筛选取法实现2~200素数求解

"用筛选取法求出2~200之间的所有素数。筛法：首先将1～n个数为数组置初值。2的倍数不是素数，置0；3的倍数不是素数，置0；5的倍数不是素数，置0；....，依次类推，最后将数组中不是0的元素输出。" 在C++程序设计中，求解素数是常见的算法问题。筛选取法，也称为埃拉托斯特尼筛法（Sieve of Eratosthenes），是一种有效的方法来找到一个给定范围内的所有素数。该方法基于以下原理：从最小的素数2开始，将它的所有倍数标记为非素数，然后移动到下一个未标记的数（即下一个素数），重复此过程直到处理完所有数。 在这个例子中，我们求的是2到200之间的素数。以下是使用筛选取法的步骤： 1. 创建一个大小为201的整型数组，初始化所有元素为1，表示它们可能是素数。 2. 从2开始，将2的倍数（2的2倍、3倍等）设为0，因为它们不是素数。 3. 移动到下一个未被标记的数，即3，将3的倍数设为0。 4. 继续这个过程，下一个未被标记的数是5，将5的倍数设为0。 5. 这样一直进行下去，直到我们处理到根号200（因为大于这个数的因数不会影响小于或等于200的数）。 6. 最后，数组中值为1的索引对应的数就是素数。 以下是简化的筛选取法的C++代码实现： ```cpp #include <iostream> #include <vector> std::vector<int> sieveOfEratosthenes(int n) { std::vector<bool> isPrime(n + 1, true); for (int i = 2; i * i <= n; ++i) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } std::vector<int> primes; for (int i = 2; i <= n; ++i) { if (isPrime[i]) { primes.push_back(i); } } return primes; } int main() { int limit = 200; std::vector<int> result = sieveOfEratosthenes(limit); for (int prime : result) { std::cout << prime << " "; } return 0; } ``` 这段代码创建了一个布尔类型的数组`isPrime`，用于标记每个数是否为素数。接着，它遍历数组，将每个素数的倍数标记为非素数。最后，收集并返回所有标记为素数的数。 C++作为一种强大的编程语言，结合了高级语言的抽象能力和低级语言的性能优势。它支持面向对象编程，提供了丰富的标准库，使得程序员能够编写高效、可维护的代码。同时，C++程序在不同平台间的可移植性良好，这也是它被广泛应用于系统编程和大型软件开发中的原因之一。 C++的发展历程也体现了编程语言不断演进的趋势。从早期的BCPL和B语言，到后来的C语言，再到C++的出现，这些语言的演变都旨在提高开发效率、增强可读性和优化性能。C++在继承C语言优点的同时，引入了类、模板、异常处理等特性，使其更适合构建复杂系统。随着计算机技术的不断发展，C++也在不断地进行版本更新，如C++11、C++14、C++17和C++20等，引入了更多现代化的编程特性，以满足现代软件工程的需求。