采用筛法求出100之内的所有素数。 要求 使用C++实现 输出100以内的素数,每行输出10个数
时间: 2023-09-03 18:07:39 浏览: 124
![CPP](https://csdnimg.cn/release/download/static_files/pc/images/minetype/UNKNOWN.png)
筛选法确定100以内的素数并输出
以下是使用筛法求出100以内的所有素数,并每行输出10个数的C++代码:
```c++
#include <iostream>
using namespace std;
int main() {
const int n = 100;
bool isPrime[n + 1];
for (int i = 2; i <= n; i++) {
isPrime[i] = true;
}
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
cout << i << " ";
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
if (i % 10 == 1) {
cout << endl;
}
}
return 0;
}
```
在这个代码中,我们首先定义了一个布尔数组isPrime,用于记录每个数是否是素数。然后初始化所有数为素数(除了1以外),接着从2开始遍历数组,如果当前数是素数,则输出它,并将它的倍数标记为非素数。最后,如果输出的数的个数是10的倍数,则输出一个换行符。
需要注意的是,我们使用筛法求素数的时间复杂度是O(nloglogn),比试除法求素数的时间复杂度O(nsqrt(n))更快。
阅读全文
相关推荐
![](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)
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.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)