在C++中如何使用筛选法高效地找到2到200之间的所有素数?请提供详细的算法描述和示例代码。
时间: 2024-11-01 21:16:52 浏览: 9
筛选法是一种古老而有效的算法,用于找到一定范围内的所有素数。在C++中实现此算法,可以使用埃拉托斯特尼筛法(Sieve of Eratosthenes),它的核心思想是通过排除法来确定素数。算法的步骤如下:
参考资源链接:[C++程序设计:筛选取法实现2~200素数求解](https://wenku.csdn.net/doc/1fmj2j2gau?spm=1055.2569.3001.10343)
\n1. 创建一个布尔数组,大小为n+1(本例中n为200),初始化所有元素为true,表示所有数都可能是素数。
\n2. 从2开始,遍历这个数组。对于每一个被标记为true的数i,将其所有的倍数(从i*i开始,每次增加i)标记为false,因为这些数不可能是素数。
\n3. 遍历完成后,数组中值仍为true的索引即为素数。
\n以下是使用C++实现的示例代码:
\n```cpp
#include <iostream>
#include <vector>
using namespace std;
void sieveOfEratosthenes(int n) {
vector<bool> primes(n + 1, true); // 初始化所有数字为素数
for (int p = 2; p * p <= n; p++) { // 优化:只需检查到√n即可
if (primes[p]) {
for (int i = p * p; i <= n; i += p) {
primes[i] = false; // 将p的倍数标记为非素数
}
}
}
// 输出所有素数
for (int p = 2; p <= n; p++) {
if (primes[p]) {
cout << p <<
参考资源链接:[C++程序设计:筛选取法实现2~200素数求解](https://wenku.csdn.net/doc/1fmj2j2gau?spm=1055.2569.3001.10343)
阅读全文