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

"《C++清华大学-谭浩强》中的筛选取法求素数方法" 在C++编程中，筛选取法（Sieve of Eratosthenes）是一种经典算法，用于找出一个范围内所有素数。这个方法由古希腊数学家埃拉托斯特尼提出，故得名埃拉托斯特尼筛法。在本例中，我们将探讨如何用这种算法求解2至200之间的所有素数。 筛选取法的基本思想是：从最小的素数2开始，标记2的所有倍数为非素数；接着找到下一个未被标记的数，即3，再标记3的所有倍数；重复此过程，直到所有小于或等于给定范围的数都被处理。最后，未被标记的数就是素数。 以下是一个简单的C++实现过程： 1. 创建一个足够大的数组，长度为n+1（这里n为200），并将所有元素初始化为1，表示它们可能是素数。 2. 从2开始，遍历数组。对于每个数i，如果它的值为1（表示它是素数），则将它的所有倍数（2*i, 3*i, ..., n/i*i）标记为0（表示它们不是素数）。 3. 遍历完成后，数组中值为1的索引位置对应的数就是素数。 具体代码示例： ```cpp #include <iostream> using namespace std; int main() { const int n = 200; bool isPrime[n + 1]; memset(isPrime, true, sizeof(isPrime)); // 初始化数组 for (int i = 2; i * i <= n; ++i) { if (isPrime[i]) { // i 是素数 for (int j = i * i; j <= n; j += i) { isPrime[j] = false; // 将i的倍数标记为非素数 } } } cout << "素数列表："; for (int i = 2; i <= n; ++i) { if (isPrime[i]) { cout << i << " "; } } return 0; } ``` 这段代码首先初始化一个布尔数组`isPrime`，然后用两层循环进行筛选。外层循环负责遍历可能的素数，内层循环负责标记这些素数的倍数。最后，输出数组中值为`true`的对应数字，即素数。 C++作为一门强大的编程语言，既拥有高级语言的抽象特性，如类和对象，也有低级语言的灵活性，如指针操作。这使得C++在游戏开发等领域得到广泛应用。C++程序设计强调结构化编程，它提供的丰富的运算符和数据结构使得程序设计更加高效且可移植性强。然而，C++的语法相对自由，对于初学者来说，理解并掌握它可能需要更多的时间和实践。 在C++入门阶段，学习和理解筛选取法这样的算法是非常有益的，因为它不仅可以帮助理解基本的编程概念，还能锻炼逻辑思维能力。随着编程技能的提升，可以尝试更复杂的游戏开发项目，利用C++的强大性能和灵活性创建出各种复杂的游戏场景和逻辑。