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

在C++基础教程中，学习者可以掌握如何利用筛选法求出一个范围内的素数，如2~200之间的素数。筛选法是一种高效的算法，它的核心思想是利用数组来标记一个数是否为素数。步骤如下： 1. 初始化数组：首先创建一个大小为2到n（这里是200）的数组，所有的初始值设为1，表示这些数都可能是素数。 2. 素数标记：从2开始，遍历数组，对于每个数i（从2到√n），如果i是素数（即尚未被标记），则将其倍数（如2i, 3i, 5i等）在数组中的对应位置标记为0，因为这些倍数都不是素数。例如，2的倍数从4开始，4, 6, 8...都应被标记；3的倍数从6开始，6, 9, 12...等。 3. 筛选过程：重复上述过程，直到遍历到√n。因为如果一个数n有因子大于√n，那么一定有一个小于√n的因子未被标记。所以，遍历到这个范围就足够确定一个数是否为素数。 4. 输出结果：遍历结束后，数组中未被标记为0的元素即为素数。比如，2, 3, 5, 7, 11, 13, ..., 19, 23, ..., 199。 在C++实现这一算法时，可以使用循环和条件判断来完成数组的更新和素数的查找。下面是一个简单的C++代码示例： ```cpp #include <iostream> #include <vector> using namespace std; void sieveOfEratosthenes(int n) { vector<bool> primes(n+1, true); // 初始化数组为素数 for (int p = 2; p * p <= n; ++p) { if (primes[p]) { // 如果p是素数 for (int i = p * p; i <= n; i += p) { primes[i] = false; // 标记p的倍数为非素数 } } } // 输出素数 for (int p = 2; p <= n; ++p) { if (primes[p]) { cout << p << " "; } } } int main() { sieveOfEratosthenes(200); return 0; } ``` 通过这段代码，我们可以看到C++语言的优势，如丰富的运算符支持，数据结构的灵活性，以及良好的可移植性。C++允许程序员编写高效且结构清晰的代码，同时也提供了一定程度的灵活性，适合处理复杂问题，如这个素数筛选算法。学习者在实践中会逐渐熟悉C++的语法结构和调试技巧，提升编程能力。