在C++程序设计中,筛选取法是一种经典的方法用于找出一定范围内(如2~200)的所有素数。这种方法基于数学原理,通过预先初始化一个数组,将所有可能的非素数(即合数)标记为0,然后仅保留那些未被标记的数作为素数。以下是用C++实现这一算法的一个步骤:
首先,介绍C++语言的背景和发展。C++起源于20世纪70年代,由Dennis Ritchie和Brian Kernighan在BCPL和B语言的基础上创建,最初为UNIX操作系统设计。C++继承了C语言的优点,如结构化编程、灵活性、高效性和可移植性,但添加了面向对象特性,使其成为更强大的编程语言。
C语言的主要特性包括:
1. 结构化编程:C++语法简洁,易于理解和编写,适用于大型系统和小型控制程序,甚至科学计算。
2. 高级与低级结合:支持丰富的运算符,包括算术、逻辑和位操作,以及灵活的数据结构,使得C++程序功能强大且执行效率高。
3. 可移植性强:编写的C++程序能在不同型号和性能级别的计算机上运行,无需大量修改。
4. 程序设计自由度高:对于有经验的程序员,这提供了更大的灵活性;但对于初学者,理解和调试可能会有挑战,需要逐步熟悉语法规则。
接下来,具体到筛选取素数的C++代码实现,可以按照以下步骤进行:
1. 初始化一个大小为n+1的布尔型数组(比如bool primes[201]),其中primes[i]表示i是否为素数,默认值设为true,假设2~n范围内的数都可能是素数。
2. 从2开始,遍历数组。对于每个素数p,将它的倍数(p*p到n)标记为非素数,即primes[p*i] = false。这是因为除了1和自身,一个数的倍数不可能是素数。
3. 遍历结束后,数组中primes[i]为true的i值即为2~n范围内的素数。在循环中,可以使用while或for循环,从2开始,每次递增p,直到p*p > n。
4. 打印出所有找到的素数,可以通过循环遍历数组,只输出primes[i]为true的i值。
下面是一个简单的C++代码示例:
```cpp
#include <iostream>
#include <vector>
bool isPrime(int num, bool primes[]) {
if (num <= 1)
return false;
if (num == 2 || primes[num])
return true;
for (int i = 2; i * i <= num; ++i) {
if (primes[i])
primes[num * i] = false;
}
return primes[num];
}
int main() {
const int limit = 200;
std::vector<int> primeNumbers;
bool primes[limit + 1];
std::fill(primes, primes + limit + 1, true); // 初始化所有数为素数
for (int i = 2; i <= limit; ++i) {
if (isPrime(i, primes)) {
primeNumbers.push_back(i);
}
}
for (const auto& num : primeNumbers) {
std::cout << num << " ";
}
return 0;
}
```
这段代码首先创建了一个布尔数组primes,然后使用isPrime函数根据筛选取法找到素数,最后输出结果。通过这种方法,可以有效地找出给定范围内的素数,展示了C++在处理数值计算问题中的应用。