如何使用C++实现埃拉托斯特尼筛法求解2到200间的所有素数?请提供完整的代码实现。
时间: 2024-11-29 16:19:47 浏览: 16
埃拉托斯特尼筛法(Sieve of Eratosthenes)是一种高效的算法,用于查找小于或等于给定数N的所有素数。在C++中实现此算法,你可以参考《C++程序设计:筛选取法实现2~200间素数》一书,其中详细介绍了该算法的原理和C++代码实现。下面是具体的实现步骤和代码:
参考资源链接:[C++程序设计:筛选取法实现2~200间素数](https://wenku.csdn.net/doc/44cv8q7p4e?spm=1055.2569.3001.10343)
首先,需要包含头文件,并声明一个足够大的布尔数组,用于表示每个数是否为素数:
```cpp
#include <iostream>
#include <cmath>
using namespace std;
#define N 200
int main() {
bool prime[N + 1];
int i, j;
memset(prime, true, sizeof(prime)); // 初始化数组所有值为true,假设都是素数
for (i = 2; i <= sqrt(N); i++) {
if (prime[i] == true) {
for (j = i * i; j <= N; j += i)
prime[j] = false; // 标记i的倍数不是素数
}
}
cout <<
参考资源链接:[C++程序设计:筛选取法实现2~200间素数](https://wenku.csdn.net/doc/44cv8q7p4e?spm=1055.2569.3001.10343)
阅读全文