埃氏筛法c++
时间: 2023-06-29 17:16:05 浏览: 65
以下是C++实现的埃氏筛法,可以用于求解素数:
```c++
#include <iostream>
#include <vector>
using namespace std;
vector<bool> sieve_of_eratosthenes(int n) {
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
return is_prime;
}
int main() {
int n;
cin >> n;
vector<bool> is_prime = sieve_of_eratosthenes(n);
for (int i = 0; i <= n; ++i) {
if (is_prime[i]) {
cout << i << " ";
}
}
return 0;
}
```
输入一个正整数n,输出小于等于n的所有素数。其中is_prime[i]表示i是否为素数,初始化为true。从2开始,如果is_prime[i]为true,则将i的倍数is_prime[j](j>=i*i且j<=n)全部标记为false,表示它们为合数。最后遍历is_prime数组,输出所有值为true的下标即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)