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

在C++编程领域，"用筛选取法求出2~200之间的所有素数"是一个经典的问题，它涉及到算法设计和基础数学概念。筛选法，也称为埃拉托斯特尼筛法，是一种古老且高效的寻找素数序列的方法。这种方法的核心思想是从最小的质数2开始，将它的所有倍数标记为合数（非素数），然后移动到下一个未被标记的数，即下一个质数，重复这个过程，直到达到指定范围的上限。 以下是如何在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; // 0和1不是质数 for (int i = 2; i * i <= n; ++i) { if (primes[i]) { // 如果i是质数 for (int j = i * i; j <= n; j += i) { primes[j] = false; // 将i的所有倍数标记为合数 } } } for (int i = 2; i <= n; ++i) { if (primes[i]) { std::cout << i << " "; } } } int main() { int limit = 200; sieveOfEratosthenes(limit); return 0; } ``` 在这个C++代码中，`isPrime`函数用于检查一个数是否为质数，`sieveOfEratosthenes`函数则是筛选法的实现，它使用一个布尔数组`primes`记录每个数是否为素数。通过循环遍历数组，将所有非质数的倍数标记为`false`，最后输出所有标记为`true`的数，即为2到200之间的素数。 通过这个示例，学习者不仅可以掌握C++编程的基本语法，如变量声明、条件判断、循环结构等，还能理解算法设计中的优化策略，以及如何处理大范围数据的有效性和内存管理。同时，这也展示了C++语言结构化、灵活和高效的特点，使得它在解决这类问题时表现出色。