请描述如何在C++中运用筛选法高效地找出2到200之间的所有素数,并解释其工作原理。
时间: 2024-11-23 16:35:39 浏览: 21
筛选法,也被称作埃拉托斯特尼筛法,是一种古老而有效的算法,用于找出小于或等于给定数的所有素数。该算法通过逐步标记数组中的非素数来识别素数。为了实现这一算法,可以使用布尔型数组来表示每一个数是否为素数。初始时,假设每一个数都是素数,然后依次标记其倍数为非素数。最终未被标记的数即为素数。以下是一个C++的实现示例:
参考资源链接:[C++实现筛选法求素数:从2到200](https://wenku.csdn.net/doc/4nr4jmbim0?spm=1055.2569.3001.10343)
```cpp
#include <iostream>
#include <vector>
// 函数:筛选法求素数
void SieveOfEratosthenes(int n) {
std::vector<bool> prime(n+1, true); // 布尔数组,默认所有元素都为true,表示都是素数
prime[0] = prime[1] = false; // 0和1不是素数,故标记为false
for (int p = 2; p*p <= n; p++) {
// 如果prime[p]没有被改变,那么它还是素数
if (prime[p] == true) {
// 将p的所有倍数标记为非素数
for (int i = p*p; i <= n; i += p)
prime[i] = false;
}
}
// 输出所有素数
std::cout <<
参考资源链接:[C++实现筛选法求素数:从2到200](https://wenku.csdn.net/doc/4nr4jmbim0?spm=1055.2569.3001.10343)
阅读全文