爱拉托斯散筛法c++
时间: 2023-11-24 17:51:24 浏览: 33
爱拉托斯特尼筛法(Sieve of Eratosthenes)是一种简单且古老的筛法,用于找出一定范围内的所有质数。以下是C++实现的爱拉托斯特尼筛法代码:
```c++
#include <iostream>
using namespace std;
const int m = 100;
int main() {
int a[m], n = 0;
bool b[m];
// 初始化
for (int i = 0; i < m; i++) {
b[i] = true;
}
// 筛法
for (int i = 2; i < m; i++) {
if (b[i]) {
a[n] = i;
n++;
for (int j = i * i; j < m; j += i) {
b[j] = false;
}
}
}
// 输出
cout << n << endl;
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
return 0;
}
```
该代码使用了一个布尔数组b[m]来表示每个数是否为质数,初始时所有数都被标记为true。然后从2开始遍历数组,如果当前数为质数,则将其加入到结果数组a中,并将其倍数在布尔数组中标记为false。最后输出结果数组即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)