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

在C++编程领域，谭浩强编著的教材中，常常会探讨如何利用筛选取法寻找特定范围内的素数，如2~200之间的素数。筛选法是一种高效的算法，它的基本思想是预先初始化一个数组，表示从1到n的整数，然后依次排除非素数。首先，将数组所有元素设为初始值1，表示它们都可能是素数。接下来，从2开始，对于每个素数p，将其倍数（除了自身）标记为合数（即置0），因为它们不是素数。例如： - 2的倍数（偶数）不是素数，置0； - 3的倍数不是素数，置0； - 5的倍数不是素数，置0； - ...依此类推。 在这个过程中，当遍历到某个素数p，我们只需关注那些未被标记的元素，它们就是当前p之前的素数。比如，数组中的2、3、5、7、11、13、17、19在处理完相应的倍数后，就都是2~200范围内的素数。 C++实现这个筛选法的关键在于迭代和数组操作。以下是一个简单的C++代码片段，展示了如何使用这种方法找到指定范围内的素数： ```cpp #include <iostream> using namespace std; void sieveOfEratosthenes(int n) { bool prime[n+1]; memset(prime, true, sizeof(prime)); // 初始化所有数为素数 for (int p = 2; p * p <= n; p++) { // 只需检查到√n if (prime[p]) { for (int i = p * p; i <= n; i += p) { prime[i] = false; // 将p的倍数标记为合数 } } } // 输出所有素数 for (int p = 2; p <= n; p++) { if (prime[p]) { cout << p << " "; } } } int main() { sieveOfEratosthenes(200); return 0; } ``` 通过这段代码，你可以看到C++如何结合循环和条件语句来实现筛选取法。C++语言的优势在于它的灵活性和高效性，使得这种算法能够在合理的时间复杂度内完成任务。同时，C++的结构化特性允许程序员清晰地组织代码，提高程序的可读性和维护性。 C++语言的发展历程中，它源于B语言和BCPL语言，经过多次改进和优化，逐渐成为一个广泛应用且性能强大的编程语言。它的特点包括结构化设计、接近底层的性能、良好的可移植性和相对较大的设计自由度，但也意味着对初学者有一定的学习曲线。理解C++的语法结构和规则对于编写高效、可维护的程序至关重要，尤其是调试技巧，这是成为一名优秀C++开发者不可或缺的技能。